Background and Objectives: Restless legs syndrome (RLS) is a common, underdiagnosed neurological movement disorder of undetermined etiology. The primary treatments for restless legs syndrome are pharmacological. To date, no randomized controlled trials have examined the effectiveness of an exercise program on the symptoms of RLS. Methods: Study participants (N = 41) were randomized to either exercise or control groups. 28 participants (average age 53.7; 39% males) were available and willing to begin the 12-week trial. The exercise group was prescribed a conditioning program of aerobic and lower-body resistance training 3 days per week. Restless legs symptoms were assessed by the International RLS Study Group (IRLSSG) severity scale and an ordinal scale of RLS severity at the beginning of the trial, and at 3, 6, 9, and 12 weeks. Results: Twenty-three participants completed the trial. At the end of the 12 weeks, the exercise group (N = 11) had a significant improvement in symptoms compared with the control group (N = 12) (P = .001 for the IRLSSG severity scale and P < .001 for the ordinal scale). Conclusions: The prescribed exercise program was effective in improving the symptoms of RLS.