Background and purpose: Our aim was to study not only the prevalence but more importantly the severity and the correlation between sleep quality and restless legs syndrome (RLS) in a large population of well-defined migraine patients as poor sleep presumably triggers migraine attacks. Methods: In a large cross-sectional and observational study, data on migraine and RLS were collected from 2385 migraine patients (according to the International Classification of Headache Disorders ICHD-IIIb) and 332 non-headache controls. RLS severity (International RLS Study Group severity scale) and sleep quality (Pittsburgh Sleep Quality Index) were assessed. Risk factors for RLS and RLS severity were calculated using multivariable-adjusted regression models. Results: Restless legs syndrome prevalence in migraine was higher than in controls (16.9% vs. 8.7%; multivariable-adjusted odds ratio 1.83; 95% confidence interval 1.18-2.86; P = 0.008) and more severe (adjusted severity score 14.5 ± 0.5 vs. 12.0 ± 1.1; P = 0.036). Poor sleepers were overrepresented amongst migraineurs (50.1% vs. 25.6%; P < 0.001). Poorer sleep quality was independently associated with RLS occurrence (odds ratio 1.08; P < 0.001) and RLS severity (P < 0.001) in migraine patients. Conclusion: Restless legs syndrome is not only twice as prevalent but also more severe in migraine patients, and associated with decreased sleep quality.