Reviews on cardiovascular fitness and cognition in older adults suggest that a higher level of cardiorespiratory fitness may protect the brain against the effects of aging. Although studies reveal positive effects of cardiorespiratory fitness on executive function, more research is needed to clarify the underlying mechanisms of these effects in older adults. The aim of the current study was to assess the association between cardiorespiratory fitness level, cerebral oxygenation, and cognitive performance in older adults (OAs). Seventy-four OAs (68 ± 6.3 years) gave their written, informed consent to participate in the study. Complete data was collected from 66 participants. All participants underwent a cycle ergometer maximal continuous graded exercise test in order to assess their peak power output (PPO) and a neuropsychological paper and pencil tests (Trail Making Test A and B) while changes in left prefrontal cortex oxygenation were measured with functional near-infrared spectroscopy (fNIRS). The results reveal increased cardiorespiratory fitness was associated with decreased response time (i.e., better performance) on the Trail Making Test (B) (standardized $β$ = − 0.42, p < 0.05). Cerebral oxygenation in higher fit older adults mediated the relationship with improved executive functioning (standardized $β$ = − 0.08, p < 0.05). Specifically, in older adults with higher cardiorespiratory fitness (based on a median split), cerebral oxygenation was related to executive functioning but no such relationship existed in lower fit adults.