Resting heart rate (RHR) has been an established predictor for atrial fibrillation (AF). However, the association of visit-to-visit heart rate variability (VVHRV) with new-onset AF risk over long term remains unclear. Our study investigates the relation of VVHRV to new-onset AF in general population in the prospective study of the Kailuan cohort. A total of 46,126 individuals without arrhythmia were included. They underwent 3 health examinations from 2006 to 2010 and performed follow up. VVHRV was measured by coefficient of variation (CV), variability independent of the mean (VIM), and standard deviation (SD). Participants were separately divided into 5 categories by quintiles of visit-to-visit RHR-CV, RHR-VIM and RHR-SD. Multivariate Cox regression and restricted cubic spline models were performed to establish the association between VVHRV and new-onset AF. 241 new-onset AF occurred during a median follow-up of 7.54 years. The incidence of new-onset AF in the group of the lowest (Q1) and highest quintiles (Q5) of RHR-CV were higher than that in other groups. The HRs for the new-onset AF were 2.07 (95% CI, 1.34-3.21, p < 0.01), in the highest quintile group(Q5) compared with group Q2, and 1.89(95% CI, 1.20-2.97, p < 0.01) in the lowest quintile group(Q1) compared with group Q2. The risk for new-onset AF showed a similar trend using RHR-VIM (p < 0.01) and RHR-SD (p < 0.05) parameters. Further sensitivity analyses indicated the consistent results in subjects without prior cardiovascular disease and without taking beta blockers or CCB. To match the covariates, analyses were also performed by propensity score matching, and prominent trends were also found in RHR-SD and RHR-VIM. In conclusion, the study indicated that higher and lower VVHRV were associated with the increasing risk of new-onset AF, which supporting a U-shaped curve existence.