We present the first study on the influence of exercise training on restless legs syndrome (RLS) in patients on hemodialysis (HD). Restless legs syndrome has been treated pharmacologically with satisfactory results; however, side effects and rebound phenomena have been reported. Intradialytic exercise training effectively counteracts uremia-induced catabolism; nevertheless, it remains unknown whether patients with RLS undergoing HD benefit from such programs. The aims of the current study were to evaluate the effect of 16-weeks aerobic exercise training in the severity of RLS and in the functional capacity and the quality of life of patients with RLS on HD. Fourteen patients on HD (four female, mean age 59 ± 16 years) with untreated RLS were assigned, according to their will, to either the exercise group (Ex-group, n = 7), and participated in a 16-week supervised intradialytic aerobic exercise training, or to the control group (Con-group, n = 7), and continued usual activities. Primary aim was to compare the International RLS (IRLS) study group rating scale, functional ability, and quality of life in baseline and the end of the 16 weeks. Exercise training reduced IRLS score by 42% (p = 0.02). Furthermore, it significantly improved indices of functional ability (p = 0.02), exercise capacity (p = 0.01), quality of life (p = 0.03), and sleep quality (p = 0.01). In the Con-group no changes were observed. In conclusion, aerobic exercise training is safe and efficacious in reducing RLS symptoms and improving quality of life in patients with RLS on HD.