© The Author(s), 2014. Background: Studies evaluating exercise interventions in people with multiple sclerosis (PwMS) demonstrate small to medium positive effects and large variability on a number of outcome measures. No study to date has tried to explain this variability. Objective: This paper presents a novel exploration of data examining the predictors of outcome for PwMS with minimal gait impairment following a randomised, controlled trial evaluating community-based exercise interventions (N = 242). Methods: The primary variable was the physical component of the Multiple Sclerosis Impact Scale-29, version 2 (MSIS-29, v2) after a 10-week, controlled intervention period. Predictors were identified a priori and were measured at baseline. Multiple linear regression was conducted. Results: Four models are presented lower MSIS-29, v2 scores after the intervention period were best predicted by a lower baseline MSIS-29,v2, a lower baseline Modified Fatigue Impact Score (physical subscale), randomisation to an exercise intervention, a longer baseline walking distance measured by the Six Minute Walk Test and female gender. This model explained 57.4% of the variance (F (5, 211) = 59.24, p < 0.01). Conclusion: These results suggest that fatigue and walking distance at baseline contribute significantly to predicting MSIS-29, v29 (physical component) after intervention, and thus should be the focus of intervention and assessment. Exercise is an important contributor to minimising the physical impact of MS, and gender-specific interventions may be warranted.