Restless legs syndrome (RLS) is a common neurological movement disorder that is often seen in multiple sclerosis patients. However, the association between RLS and multiple sclerosis (MS) is still unclear and RLS is not considered as one of the MS symptoms. This study was conducted to assess the frequency of RLS and its associated factors in patients with MS. This was a cross-sectional study conducted during January and April 2010. A total of 205 patients diagnosed with multiple sclerosis (164 females, 41 males, mean age 32.8 ± 8.9 years) were enrolled in the study and underwent a medical history interview and a neurological examination. The diagnosis of RLS was based on International Restless Legs Syndrome Study Group Criteria. 57 patients (27.8%) met the RLS diagnostic criteria. In 90.1% of the patients, the onset of RLS was simultaneous with or followed by MS onset. There was no significant difference between patients with and without RLS in respect of age, gender, disease duration, and MS pattern. There was an increased incidence of leg jerks before sleep in patients with RLS (P = 0.04). In patients suffering from RLS, there is greater complaint of insomnia (P = 0.03). Body mass index, history of anemia, excessive day-time somnolence, consuming caffeine-containing beverages, pregnancy numbers, smoking, and alcohol consumption were not associated with the presence of RLS. This study revealed high prevalence of RLS in MS patients. Screening of RLS in these patients should always be considered to improve management of MS.