The current study examined the effects of physical fitness and aerobic exercise on cognitive functioning and coherence of the electroencephalogram in 30 adolescents between the ages of 13 and 14 years. Participants were first classified as fit or unfit and then performed a modified Eriksen flanker task after a bout of acute exercise and after a period of relaxation. Analysis of behavioural differences between the fit and unfit groups revealed an interaction between fitness levels and acute physical exercise. Specifically, fit participants had significantly faster reaction times in the exercise condition in comparison with the rest condition; unfit, but not fit, participants had higher error rates for NoGo relative to Go trials in the rest condition. Furthermore, unfit participants had higher levels of lower alpha, upper alpha, and beta coherence in the resting condition for NoGo trials, possibly indicating a greater allocation of cognitive resources to the task demands. The higher levels of alpha coherence are of particular interest in light of its reported role in inhibition and effortful attention. The results suggest that physical fitness and acute exercise may enhance cognition by increasing the efficacy of the attentional system.