Atrial fibrillation (AF) is associated with increased morbidity and mortality. We sought to determine whether atrial premature complexes (APCs) detected during a standard exercise stress test (EST) in patients undergoing cardiac rehabilitation (CR) are associated with an increased risk of AF. The present study population comprised 6,523 consecutive patients without prior AF who participated in a CR program in a tertiary medical center in years 2009 to 2016. Multivariate analysis was used to identify the association between APCs during the baseline EST at CR and the risk for the development of AF over a mean follow-up period of 2.5 years. A total of 213 (3.7%) patients had APCs during their EST. Despite being older (mean age 63 ± 13 years old vs 58 ± 13; p <0.001, respectively), no other statistically significant differences were documented. Kaplan–Meier survival analysis showed that the rate of AF development during follow-up was significantly higher in patients with APCs at baseline EST (11%) as compared with those without APCs (5%; log-rank p <0.001 for the overall difference during follow-up). Consistently, multivariate analysis showed that patients with APCs showed >twofold increase risk for AF compared with those without APCs (hazard ratio 2.1; 95% confidence interval 1.36 to 3.25; p <0.001). In conclusion, our findings suggest that APCs detected during EST in patients participating in the CR program independently predict AF and can be used to improve risk stratification in this population.