Physical exertion is sometimes associated with changes in cognitive function. However, there is a dearth of literature on the physiological basis of these associations. PURPOSE: To determine the acute effects of intense physical exercise on executive function and prefrontal cortex brain activity, and the impact of baseline fitness on these associations. METHODS: 103 participants (F = 29, M = 74; Age = 40 ± 8) completed tests of executive function before and after undergoing a VO2max test with a Bruce Treadmill Protocol. A comparison control group of 32 participants matched for age, birth sex and fitness completed the same tests before and after active rest. Body fat % was determined via bioelectrical impedance and VO2max via gas analysis. The cognitive tests measured reaction time, control inhibition, stimulus-oriented & stimulus-independent thought, and source memory. Brain activity of the prefrontal cortex was measured during the pre- and post-exercise cognitive tests using functional Near Infrared Spectroscopy (fNIRS). RESULTS: The cohort’s mean body fat was 25 ± 7 %, Anaerobic Threshold (AT) was 28 ± 5 ml/kg/min and VO2max was 38 ± 7 ml/kg/min. At baseline, there was no association between body fat % or VO2max and cognitive test performance. However, after exercise, participants showed significantly improved cognitive speed with no decrease in accuracy (F = 28.1; p < .001). The degree to which individual participants showed this exercise-related cognitive enhancement was reflected in changes in oxygen utilisation in the prefrontal cortex, in the regions associated with performances on the individual tasks, beyond those occurring in the no-exercise control group (n = 92, α < .05, FDR corrected). In addition, the exercise-related cognitive speed improvements were significantly negatively associated with body fat % (R2 = 11.4%; p = .001) and with age (R2 = 11.0%; p = .001) and were positively correlated with VO2/kg at AT (R2 = 6.9%, p = .008) and VO2max (p = .003). CONCLUSION: Exercise improved prefrontal cortex brain activity and cognitive processing speed with no detriment to accuracy in executive function in healthy adults. Although all participants improved after exercise, those with a higher body fat percentage, lower cardiovascular fitness and older age showed proportionally less improvement.