Abstract Study Objectives To assess the frequency of restless legs syndrome (RLS), periodic limb movements during sleep (PLMS), and their overlap in a large sample of patients with multiple sclerosis (MS). To compare clinical and paraclinical findings among four subgroups of patients: RLS−/PLMS− (patients without RLS and PLMS), RLS+/PLMS− (patients with RLS and without PLMS), RLS−/PLMS (patients without RLS and with PLMS), and RLS+/PLMS+ (patients with both RLS and PLMS). Methods In this cross-sectional, observational, instrumental study, 86 patients (M/F: 27/59; mean age 48.0 ± 10.8 years) with a diagnosis of MS underwent a telephone interview assessing the five standard diagnostic criteria for RLS. Seventy-six participants underwent polysomnography (PSG) and maintenance of wakefulness test (MWT). Instrumental and clinical findings were subsequently statistically compared to investigate their association with RLS and PLMS index (PLMSI). Results RLS and PLMS (PLMSI ≥15/h) frequency in patients with MS were of 31.4% and 31.6%, respectively. Among patients with RLS, 37.5% had a PLMSI of at least 15/h. RLS−/PLMS+ group showed higher wake after sleep onset (p = 0.01), stage shifts per hour (p = 0.03), increased stage N1 (p = 0.03), and reduction in stage N3 (p = 0.01) compared to RLS−/PLMS−. RLS had no influence on clinical and PSG parameters (p = 0.45). Conclusions RLS is highly frequent in patients with MS. The frequency of PLMS is comparable to the general population. The low percentage of patients with RLS having a high PLMSI, together with the absence of correlation between RLS and female gender and older age, supports the existence of a distinct symptomatic form of RLS in MS.