Background: Evidence supporting the effectiveness of aerobic training, specific for fatigue, in severely fatigued patients with multiple sclerosis (MS) is lacking. Objective: To estimate the effectiveness of aerobic training on MS-related fatigue and societal participation in ambulant patients with severe MS-related fatigue. Methods: Patients (N = 90) with severe MS-related fatigue were allocated to 16-week aerobic training or control intervention. Primary outcomes were perceived fatigue (Checklist Individual Strength (CIS20r) fatigue subscale) and societal participation. An improvement of ≥8 points on the CIS20r fatigue subscale was considered clinically relevant. Outcomes were assessed by a blinded observer at baseline, 2, 4, 6 and 12 months. Results: Of the 89 patients that started treatment (median Expanded Disability Status Scale (interquartile range), 3.0 (2.0–3.6); mean CIS20r fatigue subscale (standard deviation (SD)), 42.6 (8.0)), 43 received aerobic training and 46 received the control intervention. A significant post-intervention between-group mean difference (MD) on the CIS20r fatigue subscale of 4.708 (95% confidence interval (CI) = 1.003– 8.412; p = 0.014) points was found in favour of aerobic training that, however, was not sustained during follow-up. No effect was found on societal participation. Conclusion: Aerobic training in MS patients with severe fatigue does not lead to a clinically meaningful reduction in fatigue or societal participation when compared to a low-intensity control intervention.