Exercise training has been proposed to counteract age-related cognitive decline through improvements in cardiorespiratory fitness (CRF hypothesis). Research has focused on cognitive domains such as attention and processing speed, and one cross-sectional study reported a positive relationship between CRF and language production. In a randomized controlled trial, we investigated whether these benefits could extend to language comprehension in healthy older adults, and whether bilinguals, for whom language processing is more costly, would exhibit greater benefits than monolinguals. 80 older English monolinguals and 80 older Norwegian-English bilinguals were randomized into either a 6-month exercise training group or to a passive control group. We assessed CRF (V̇O2peak) and language comprehension (reaction times to spoken word monitoring) in first (L1, all participants) and second language (L2, bilinguals only), before and after the exercise training intervention. We found that monolinguals in the exercise group (compared to the control group) were faster in comprehension following the intervention. Moreover, this effect was mediated by exercise-induced increases in V̇O2peak, supporting the CRF hypothesis. This extends previous cross-sectional research and establishes a causal link between exercise training and speeded comprehension in older monolinguals. However, exercise training did not affect bilingual (L1 or L2) comprehension, despite inducing increased V̇O2peak, and bilinguals in both groups were slower after the intervention period. Exploratory analyses suggested that this may be driven by participants with low L2 proficiency, but further research is needed to examine whether bilingual language processing is in fact unaffected by exercise training and its consequent improvements in CRF.