Periodic limb movement disorder (PLMD) and restless legs syndrome (RLS) are two sleep disorders characterized by abnormal leg movements and are responsible for deterioration in sleep quality. However, the prevalence of these disorders is not well known in the general population. This study aims to document the prevalence of RLS and PLMD in the general population and to identify factors associated with these conditions. Cross-sectional studies were performed in the UK, Germany, Italy, Portugal and Spain. Overall, 18,980 subjects aged 15 to 100 years old representative of the general population of these five European countries underwent telephone interviews with the Sleep-EVAL system. A section of the questionnaire assessed leg symptoms during sleep. The diagnoses of PLMD and RLS were based on the minimal criteria provided by the International Classification of Sleep Disorders. The prevalence of PLMD was 3.9% and RLS was 5.5%. RLS and PLMD were higher in women than in men. The prevalence of RLS significantly increased with age. In multivariate models, being a woman, the presence of musculoskeletal disease, heart disease, obstructive sleep apnea syndrome, cataplexy, doing physical activities close to bedtime and the presence of a mental disorder were significantly associated with both disorders. Factors specific to PLMD were: being a shift or night worker, snoring, daily coffee intake, use of hypnotics and stress. Factors solely associated with RLS were: advanced age, obesity, hypertension, loud snoring, drinking at least three alcoholic beverages per day, smoking more than 20 cigarettes per day and use of SSRI. PLMD and RLS are prevalent in the general population. Both conditions are associated with several physical and mental disorders and may negatively impact sleep. Greater recognition of these sleep disorders is needed.