Objective: Physical activity represents a promising treatment for major depressive disorder (MDD) in people with multiple sclerosis (MS). We conducted a single-blind, two-arm randomized controlled trial comparing a 12-week physical activity counseling intervention delivered primarily by telephone (n = 44) to a wait-list control group (N = 48). Method: Ninety-two adults with MS and MDD or dysthymia (M[subscript age] = 48 years; 86% female, 92% White) completed an in-person baseline assessment and were randomized to wait-list control or an intervention involving motivational-interviewing-based promotion of physical activity. The treatment group received an initial in-person session; 7 telephone counseling sessions (Weeks 1, 2, 3, 4, 6, 8, and 10), and an in-person session at Week 12. The primary outcome, treatment response, was defined as those with 50% or greater reduction in the Hamilton Depression Rating Scale (HAM-D) score. Results: Our primary hypothesis, that the proportion of responders in the treatment group would be significantly greater than in the control group, was not confirmed. However, compared with the control group, those in the treatment group evidenced significantly lower depression severity on the HAM-D, on self-reported depression, and on a measure of potential side effects and at 12 weeks were less likely to meet the criteria for MDD as set forth in the "Diagnostic and Statistical Manual of Mental Disorders" (4th ed.). Physical activity increased significantly more in the treatment condition, though it did not mediate improvement in depression severity. Conclusions: Telephone-based physical activity promotion represents a promising approach to treating MDD in MS. Further research is warranted on ways to bolster the impact of the intervention and on mediators of the treatment effect. (Contains 3 tables and 1 figure.)