Several publications have described differences in cross-sectional comparisons of gut microbiota between patients with Parkinson's disease and control subjects, with considerable variability of the reported differentially abundant taxa. The temporal stability of such microbiota alterations and their relationship to disease progression have not been previously studied with a high-throughput sequencing based approach. We collected clinical data and stool samples from 64 Parkinson's patients and 64 control subjects twice, on average 2·25 years apart. Disease progression was evaluated based on changes in Unified Parkinson's Disease Rating Scale and Levodopa Equivalent Dose, and microbiota were characterized with 16S rRNA gene amplicon sequencing. We compared patients to controls, and patients with stable disease to those with faster progression. There were significant differences between microbial communities of patients and controls when corrected for confounders, but not between timepoints. Specific bacterial taxa that differed between patients and controls at both timepoints included several previously reported ones, such as Roseburia, Prevotella and Bifidobacterium. In progression comparisons, differentially abundant taxa were inconsistent across methods and timepoints, but there was some support for a different distribution of enterotypes and a decreased abundance of Prevotella in faster-progressing patients. The previously detected gut microbiota differences between Parkinson's patients and controls persisted after 2 years. While we found some evidence for a connection between microbiota and disease progression, a longer follow-up period is required to confirm these findings.