Background: Depression in multiple sclerosis (MS) patients is common but may stay untreated. Physical limitations impede face-to-face treatment. Internet-based treatment is therefore a promising tool for treating depression in MS. Objectives: To investigate effectiveness of a guided Internet-based problem-solving treatment (IPST) for depressed MS patients. Methods: MS patients with moderate or severe depressive symptoms were randomly assigned to IPST or a wait list control. Primary outcome was the change in depressive symptoms defined by a change in sum score on the Beck Depression Inventory Second Edition (BDI-II). Assessments took place at baseline (T0), within a week after the intervention (T1), and at 4 months follow-up (T2). Analyses were based on the intention-to-treat principle. Results: A total of 171 patients were randomized to IPST (n = 85) or a wait list control (n = 86). T1 was completed by 152 (89%) and T2 by 131 patients (77%). The IPST group and wait list control showed large significant improvements in depressive symptoms, but no differences were found between groups at T1 (d = 0.23; 95% confidence interval (CI) = (−4.03, 1.08); p = 0.259) and T2 (d = 0.01; 95% CI = (−2.80, 2.98); p = 0.953). Conclusion: We found no indication that IPST for MS patients with moderate or severe depression is effective in reducing depressive symptoms compared to a waiting list. Large improvements in the wait list control were unexpected and are discussed.