Background Only few aerobic exercise intervention trials specifically targeting cognitive functioning have been performed in multiple sclerosis. Objective and Methods This randomized controlled trial with 34 patients in the intervention group (IG) (mean: 38.2 years (±9.6)) and 34 patients in the control group (CG) (mean: 39.6 years (±9.7)) aimed to determine the effects of aerobic exercise on cognition in relapsing-remitting multiple sclerosis (RRMS). The primary outcome was verbal learning assessed by the verbal learning and memory test (VLMT). Patients were randomized to an IG or a waitlist CG. Patients in the IG exercised according to an individually tailored training schedule (with two to three sessions per week for 12 weeks). The primary analysis was carried out using the intention-to-treat (ITT) sample with ANCOVA adjusting for baseline scores. Results A total of 77 patients with RRMS were screened and 68 participants randomized (CG n = 34; IG n = 34). The sample comprised 68% females, had a mean age of 39 years, a mean disease duration of 6.3 years, and a mean expanded disability status scale of 1.8. No significant effects were detected in the ITT analysis for the primary endpoint VLMT or any other cognitive measures. Moreover, no significant treatment effects were observed for quality of life, fatigue, or depressive symptoms. Conclusion This study failed to demonstrate beneficial effects of aerobic exercise on cognition in RRMS. The trial was prospectively registered at clinicaltrials.gov (NCT02005237).