Recent studies have provided evidence for a positive association between migraine and restless legs syndrome (RLS), although the exact mechanisms and contributing factors remain unclear. A cross-sectional, case-control study was conducted, including patients with migraine (n = 262) and headache-free control subjects (n = 163). Migraine was diagnosed according to International Classification of Headache Disorders II criteria. RLS diagnosis was made based on four essential criteria as described by the International Restless Legs Syndrome Study Group. All patients completed the Migraine Disability Assessment (MIDAS) questionnaire, Beck Depression Inventory (BDI)-II scores, Pittsburgh Sleep Quality Index (PSQI), and Epworth Sleepiness Scale (ESS). A total of 210 blood samples were collected to correlate various parameters with RLS. RLS frequency was significantly greater in patients with migraine than in controls (13.7 vs. 1.8%). Migraine patients with RLS had high scores for MIDAS, BDI-II, PSQI, and ESS compared with those without RLS. In addition, migraine patients with RLS had a high rate of smoking and RLS family history, as well as increased levels of serum phosphorus and urea nitrogen compared with those without RLS. However, there was no difference in serum iron and ferritin levels between the groups. In migraine patients, logistic regression analysis revealed that positive RLS family history, BDI-II, ESS, and serum phosphorus levels were significant RLS predictors. Our study confirmed a positive association between RLS and migraine. RLS comorbidity in migraine patients was associated with insomnia, daytime sleepiness, depressive symptoms, headache-related disability, and increased serum phosphorus levels. These findings may provide a better understanding of RLS pathogenesis in migraine.