Introduction: Autonomic nervous system (ANS) dysfunction contributes to several non-motor symptoms of Parkinson's disease (PD). In addition, ANS plays a role in the genesis and maintenance of atrial fibrillation (AF). This study investigated the temporal association between PD and AF. Methods: Data were obtained from the National Health Insurance Research Database of Taiwan. In total, 15,375 patients with newly diagnosed PD were matched with four controls each based on the propensity score. This study was bidirectional. A case-control study for the odds ratio (OR) of AF before PD and within 2 years of PD diagnosis was evaluated through conditional logistic regression. Furthermore, a cohort study on the subdistribution hazard ratio (SHR) for new-onset AF 2 years after PD diagnosis was evaluated using competing risk analysis. Results: In the case-control study, PD was found to be significantly comorbid with AF (adjusted OR: 1.15, 95% confidence interval [CI]: 1.04–1.28). Subgroup analysis demonstrated that this association consistently presented in the absence of confounding factors of AF. In the cohort study, people with PD were found to have a lower risk of AF (adjusted SHR: 0.92, 95% CI: 0.86–0.98). However, a consistent association was not observed between the confounding factors of AF and PD during the subgroup analysis. Conclusions: This study demonstrated that the premotor and early stages of PD were comorbid with AF, whereas the risk of AF was lower in the later stages. Thus, AF might be a premotor predictive biomarker and comorbidity of early PD.