Slowed cognitive processing speed (CPS) is a common and debilitating consequence of multiple sclerosis (MS) that is notoriously difficult to treat. As such, we undertook a systematic line of research that indicated that supervised, progressive treadmill walking exercise (TMWX) training might improve CPS and brain functioning among fully-ambulatory persons with MS. The current study will be the first adequately-powered, single-blind randomized controlled trial (RCT) that examines the efficacy of 12-weeks of TMWX training compared with an active control condition on CPS, thalamocortical brain connectivity (based on resting-state fMRI), and exploratory functional outcomes in 88 fully-ambulatory persons with MS who present with slowed CPS. The intervention condition involves supervised, progressive TMWX training 3 times/week over 12-weeks; this initially involves 15-min of light-to-moderate intensity TMWX that progresses up to 40-min of vigorous intensity TMWX. The active control condition involves supervised, minimal intensity, stretching-and-resistance exercise that will be delivered on the same frequency as the intervention condition. The primary study outcomes involve Symbol Digit Modalities Test performance (i.e., CPS) and fMRI-based measures of thalamocortical resting-state functional connectivity. Exploratory study outcomes involve measures of community participation, activities of daily living, quality of life, and functional mobility. All study outcomes will be administered before and after the 12-week study period by treatment-blinded assessors. If successful, the current study will provide the first Class I evidence for the effects of TMWX training as an approach for improving CPS and its neural correlate, and possibly mitigating the impact of slowed CPS on functional outcomes in MS.