© 2017 Background Mobility disability is a common, debilitating feature of multiple sclerosis (MS). Exercise training has been identified as an approach to improve MS-related mobility disability. However, exercise randomized controlled trials (RCTs) on mobility in MS have generally not selectively targeted those with the onset of irreversible mobility disability. Objectives The current multi-site RCT compared the efficacy of 6-months of supervised, multimodal exercise training with an active control condition for improving mobility, gait, physical fitness, and cognitive outcomes in persons with substantial MS-related mobility disability. Methods 83 participants with substantial MS-related mobility disability underwent initial mobility, gait, fitness, and cognitive processing speed assessments and were randomly assigned to 6-months of supervised multimodal (progressive aerobic, resistance, and balance) exercise training (intervention condition) or stretching-and-toning activities (control condition). Participants completed the same outcome assessments halfway through and immediately following the 6-month study period. Results There were statistically significant improvements in six-minute walk performance (F(2158) = 3.12, p = 0.05, ηp2 = 0.04), peak power output (F(2150) = 8.16, p < 0.01, ηp2 = 0.10), and Paced Auditory Serial Addition Test performance (F(2162) = 4.67, p = 0.01, ηp2 = 0.05), but not gait outcomes, for those who underwent the intervention compared with those who underwent the control condition. Conclusions This RCT provides novel, preliminary evidence that multimodal exercise training may improve endurance walking performance and cognitive processing speed, perhaps based on improvements in cardiorespiratory capacity, in persons with MS with substantial mobility disability. This is critical for informing the development of multi-site exercise rehabilitation programs in larger samples of persons with MS-related mobility disability.