Background: Fatigue is a common symptom in multiple sclerosis (MS) and often restricts societal participation. Cognitive behavioral therapy (CBT) may alleviate MS-related fatigue, but evidence in literature is inconclusive. Objective: To evaluate the effectiveness of CBT to improve MS-related fatigue and participation. Methods: In a multi-center, assessor-masked, randomized controlled trial, participants with severe MS related fatigue were assigned to CBT or control treatment. CBT consisted of 12 individual sessions with a psychologist trained in CBT, the control treatment consisted of three consultations with a MS nurse, both delivered over 16 weeks. Assessments were at baseline, 8, 16 (i.e. post-intervention), 26, and 52 weeks post-baseline. Primary outcomes were the Checklist Individual Strength-fatigue subscale (CIS20r fatigue) and the Impact on Participation and Autonomy questionnaire (IPA). Data were analyzed according to the intention-to-treat principle, using mixed-model analysis. Results: Between 2011 and 2014, 91 patients were randomized (CBT: n = 44; control: n = 47). Between group analysis showed a positive post-intervention effect for CBT on CIS20r fatigue (T16: −6.7 (95% confidence interval (CI) = −10.7; −2.7) points) that diminished during follow-up (T52: 0.5 (95% CI = −3.6; 4.4)). No clinically relevant effects were found on societal participation. Conclusion: Severe MS-related fatigue can be reduced effectively with CBT in the short term. More research is needed on how to maintain this effect over the long term.