Progression of atrial fibrillation (AF) is associated with worsened prognosis for cardiovascular events and mortality. Exercise-based-cardiac rehabilitation programmes have shown preliminary promise for primary and secondary prevention of AF. Yet, such interventions are typically reserved for patients with acute coronary syndrome or undergoing revascularization. Using a retrospective cohort design, the present study investigated the association of exercise-based cardiac rehabilitation on the progression of paroxysmal to sustained AF, compared to propensity-matched controls. Patients with a diagnosis of paroxysmal AF were compared between those with and without an electronic medical record of exercise-based cardiac rehabilitation within 6-months of diagnosis. Using cox regression models, we ascertained odds of 2-year incidence for AF progression. This cohort of 9808 patients with paroxysmal AF demonstrated that exercise-based cardiac rehabilitation was associated with 26% lower odds of AF progression (odds ratio 0.74, 95% CI 0.66-0.83) compared to propensity-matched controls. This beneficial effect seemed to vary across patient subgroups. In conclusion, findings revealed that exercise-based cardiac rehabilitation was associated with significantly lower odds of progression from paroxysmal to sustained AF at 2-years follow-up compared to propensity-matched controls.