Introduction: Cognitive processing speed impairment (PSI) is common and debilitating in persons with multiple sclerosis (MS). Exercise training has been proposed as a behavioral approach for possibly managing MS-related processing speed dysfunction, largely based on cross-sectional studies of the relationship of cardiorespiratory fitness and cognitive processing speed. However, there is minimal evidence supporting exercise training as a treatment for MS-related PSI, as the vast majority of the existing studies have examined exercise and cardiorespiratory fitness effects on cognition in samples of noncognitively impaired persons with MS. To that end, the current cross-sectional investigation examined whether cardiorespiratory fitness was differentially associated with processing speed in persons with MS with and without PSI. Methods: Sixty-four persons with MS undertook the Symbol Digit Modalities Test for establishing groups with and without MS-related PSI, a modified flanker task for measuring processing speed performance, and an incremental exercise test to exhaustion on a cycle ergometer for measuring cardiorespiratory fitness in a single testing session. Bivariate correlations were performed on cardiorespiratory fitness and processing speed outcomes in PSI group subsamples. Results: In the sample without PSI, cardiorespiratory fitness was not significantly associated with processing speed (P = 0.08). However, in the sample with PSI, cardiorespiratory fitness was significantly associated with processing speed (P = 0.01), such that lower cardiorespiratory fitness was strongly associated with slower processing speed. Conclusions: This study provides preliminary evidence of a significant association between cardiorespiratory fitness and processing speed in persons with MS-related PSI. Such an investigation provides the first direct support for aerobic exercise training as a possible behavioral approach for managing/treating MS-related cognitive impairment, beyond merely improving cognitive performance.