Growing evidence supports the use of physical training interventions to improve both physical and cognitive performances in healthy older adults. Few studies have examined the impact of aerobic exercise on Stroop task performance, a measure of executive functions. In the current 3-month aerobic training study, 50 older adults (mean age = 67.96 ± 6.25 years) were randomly assigned to either a three-month physical training group or to a control group (waiting list). Training sessions were 3 times per week for 60 minutes. All participants completed pre- and post-test measures of cognitive performance using the modified Stroop task and physical performance (Rockport one-mile test). Compared to controls, the training group showed significant improvements in physical capacity ( P < 0.001) and enhanced Stroop performance, but only in the inhibition/switching condition ( P < 0.03). Furthermore, the increase in aerobic capacity induced by the training regimen correlated negatively with reaction time in the inhibition/switching condition of the Stroop task at posttest ( r = −0.538; P = 0.007). Importantly, the reported gains in cognitive performance were observed after only three months of physical training. Taken together, the results suggest that even short-term physical interventions can enhance older adults' executive functions.