The current study examined the effects of cardiorespiratory fitness, identified with a continuous graded cycle ergometry, and aerobic exercise on cognitive functioning and entropy of the electroencephalogram (EEG) in 30 adolescents between the ages of 13 and 14 years. Higher and lower fit participants performed an executive function task after a bout of acute exercise and after rest while watching a film. EEG entropy, using the sample entropy measure, was repeatedly measured during the 1500 ms post-stimulus interval to evaluate changes in entropy over time. Analysis of the behavioral data for lower and higher fit groups revealed an interaction between fitness levels and acute physical exercise. Notably, lower fit, but not higher fit, participants had higher error rates (ER) for No Go relative to Go trials in the rest condition, whereas in the acute exercise condition there were no differences in ER between groups; higher fit participants also had significantly faster reaction times in the exercise condition in comparison with the rest condition. Analysis of EEG data revealed that higher fit participants demonstrated lower entropy post stimulus than lower fit participants in the left frontal hemisphere, possibly indicating increased efficiency of early stage stimulus processing and more efficient allocation of cognitive resources to the task demands. The results suggest that EEG entropy is sensitive to stimulus processing demands and varies as a function of physical fitness levels, but not acute exercise. Physical fitness, in turn, may enhance cognition in adolescence by facilitating higher functionality of the attentional system in the context of lower levels of frontal EEG entropy.