Sleep apnea has been recognized as a factor predisposing to atrial fibrillation recurrence and progression. The effect of other sleep-disturbing conditions on atrial fibrillation progression is not known. We sought to determine whether frequent periodic leg movement during sleep is a risk factor for progression of atrial fibrillation. In this retrospective study, patients with atrial fibrillation and a clinical suspicion of restless legs syndrome who were referred for polysomnography were divided into two groups based on severity of periodic leg movement during sleep: frequent (periodic movement index >35/h) and infrequent (≤35/h). Progression of atrial fibrillation to persistent or permanent forms between the two groups was compared using Wilcoxon rank-sum test, chi-square tests and logistic regression analysis. Of 373 patients with atrial fibrillation (77% paroxysmal, 23% persistent), 108 (29%) progressed to persistent or permanent atrial fibrillation during follow-up (median, 33 months; interquartile range, 16-50). Compared to patients with infrequent periodic leg movement during sleep (n=168), patients with frequent periodic leg movement during sleep (n=205) had a higher rate of atrial fibrillation progression (23% vs. 34%; p=0.01). Patients with frequent periodic leg movement during sleep were older and predominantly male; however, there were no significant differences at baseline in clinical factors that promote atrial fibrillation progression between both groups. On multivariate analysis, independent predictors of atrial fibrillation progression were persistent atrial fibrillation at baseline, female gender, hypertension and frequent periodic leg movement during sleep. In patients with frequent periodic leg movement during sleep, dopaminergic therapy for control of leg movements in patients with restless legs syndrome reduced risk of atrial fibrillation progression. Frequent leg movement during sleep in patients with restless legs syndrome is associated with progression of atrial fibrillation to persistent and permanent forms.