Frailty is characterized by an increased vulnerability to adverse health events. Executive function impairment is an early sign of progression towards cognitive impairments. Whether frailty is associated with executive function and the associated mechanisms are unclear. We test the hypothesis that higher frailty is associated with worse executive function (Trail Making Test) and if aerobic fitness, prefrontal cortex oxygenation (ΔO2Hb), or middle-cerebral artery velocity (MCAv) impact this association. Forty-one (38 females) cognitively health older adults (70.1 ± 6.3 years) completed a Trail task and 6-min walk test. Prefrontal cortex oxygenation was measured during the Trail task (via functional near-infrared spectroscopy) and MCAv in a sub-sample (n=26, via transcranial Doppler). A 35-item frailty index was used. Frailty was independently, non-linearly related to trail B performance (Frailty2: β=1927 [95% CI: 321–3533], p = 0.02), with the model explaining 22% of the variance of trail B time (p = 0.02). Aerobic fitness was an independent predictor of trail B (β=−0.05 [95% CI: −0.10–0.004], p = 0.04), but age and ΔO2Hb were not (both, p textgreater 0.78). Frailty was positively associated with the difference between trails B and A (β=105 [95% CI: 24–186], p = 0.01). Frailty was also associated with a higher peak MCAv (ρ = 0.40, p = 0.04), but lower ΔO2Hb-peakMCAv ratio (ρ = −0.44, p = 0.02). Higher frailty levels are associated to worse Trail times after controlling for age, aerobic fitness, and prefrontal oxygenation. High frailty level may disproportionately predispose older adults to challenges performing executive function tasks that may manifest early as a compensatory higher MCAv despite worse executive function, and indicate a greater risk of progressing to cognitive impairment.