Background: Restless Legs Syndrome is a very common disorder in hemodialysis patients. Restless Legs Syndrome negatively affects quality of life; however it is not clear whether this is due to mental or physical parameters and whether an association exists between the syndrome and parameters affecting survival. Methodology/Principal Findings: Using the Restless Legs Syndrome criteria and the presence of Periodic Limb Movements in Sleep (PLMS/h >15), 70 clinically stable hemodialysis patients were assessed and divided into the RLS (n = 30) and non-RLS (n = 40) groups. Physical performance was evaluated by a battery of tests: body composition by dual energy X ray absorptiometry, muscle size and composition by computer tomography, while depression symptoms, perception of sleep quality and quality of life were assessed through validated questionnaires. In this cross sectional analysis, the RLS group showed evidence of thigh muscle atrophy compared to the non-RLS group. Sleep quality and depression score were found to be significantly impaired in the RLS group. The mental component of the quality of life questionnaire appeared significantly diminished in the RLS group, reducing thus the overall quality of life score. In contrast, there were no significant differences between groups in any of the physical performance tests, body and muscle composition. Conclusions: The low level of quality of life reported by the HD patients with Restless Legs Syndrome seems to be due mainly to mental health and sleep related aspects. Increased evidence of muscle atrophy is also observed in the RLS group and possibly can be attributed to the lack of restorative sleep.