(1) Background: Cognitive impairment is highly prevalent in multiple sclerosis (MS). Staying physically fit may be associated with preservation of cognitive performance in persons with MS (pwMS); (2) Objective: To investigate the association between aerobic capacity and the cognitive domains of information processing, learning and memory, and verbal fluency as well as single and composite z-scores of the Brief Repeatable Battery of Neuropsychological tests (BRBNT) in pwMS; (3) Methods: All subjects first performed the BRBNT and then a maximal oxygen consumption (VO₂-max) test on a bicycle ergometer as a measure of aerobic capacity. Simple and multiple (adjusting for age, sex, and education level) regression analyses were performed to evaluate the relationship between aerobic capacity and cognitive performance in different domains. Published international norms were used to compute z-scores for each individual and composite BRBNT score. Furthermore, cognitive impairment was defined as one or more z-scores ≤-1.5 standard deviation (SD) of healthy controls; (4) Results: Eighty-four subjects were included (44.9 ± 9 years, 16.3 ± 2 education years, Expanded Disability Status Scale (EDSS): 2.6 ± 1.4, MS-type (relapsing-remitting, primary progressive, or secondary progressive): 73/6/5, disease duration: 9.9 ± 7 years, VO₂-max: 28.4 ± 7.0 mL O₂/min/kg). No significant associations between aerobic capacity and cognitive performance in the individual BRBNT tests were found, except that a weak relationship was found between aerobic capacity and the composite processing speed z-score (R² = 0.06, p = 0.02). The average global BRBNT z-score (-0.2 ± 0.66) was not associated with aerobic capacity. Comparison of the cognitively impaired group (34.5%) with the nonimpaired group (65.5%) showed lower aerobic capacity in the impaired group (25.9 ± 1 vs. 29.7 ± 1 mLO₂/min/kg, p = 0.02); (5) Conclusions: Limited support was found for an association between performance in most cognitive domains and aerobic capacity in the present MS group with a third of patients showing signs of cognitive impairments.