Background - Exercise programmes that can demonstrate evidence of long-lasting clinical effectiveness are needed for people with multiple sclerosis (PwMS). Objective - The objective of this study was to assess the effects of a practically implemented exercise programme on self-directed exercise behaviour and important health outcomes in PwMS to nine months of follow-up. Methods - We conducted a parallel-arm, randomised controlled trial: 120 PwMS (Expanded Disability Status Scale (EDSS) 1.0-6.5) randomised to a three-month exercise intervention plus usual care, or usual care only. Two supervised plus one home-exercise session (weeks 1-6) were followed by one supervised and two home-exercise sessions (weeks 7-12). Cognitive-behavioural techniques promoted long-term exercise behaviour change. Outcomes were blindly assessed at baseline and at three and nine months after randomisation. The primary outcome was self-reported exercise behaviour (Godin Leisure Time Exercise Questionnaire (GLTEQ)). Secondary outcomes included fatigue and health-related quality of life (HRQoL). Results - The intervention increased self-reported exercise (9.6 points; 95% CI: 2.0 to 17.3 points; p = 0.01) and improved fatigue (p <0.0001) and many HRQoL domains (p ≤ 0.03) at three months. The improvements in emotional well-being (p = 0.01), social function (p = 0.004) and overall quality of life (p = 0.001) were sustained for nine months. Conclusion - This pragmatic approach to implementing exercise increases self-reported exercise behaviour, improves fatigue and leads to a sustained enhancement of HRQoL domains in PwMS.