The aims of this study were to examine the effects of aerobic exercise on measures of executive performance and their relationships with changes in cardiorespiratory fitness, cardiac vagal control (heart rate variability) and psychological variables. Thirty-six sedentary seniors aged 60–75 years were randomly assigned to a swimming and aquaerobics program or a stretching program two times a week for 21 weeks. Executive functions (inhibition, updating of working memory and cognitive flexibility) and cardiorespiratory fitness (estimated VO2max) were assessed at the start, after 10 weeks of program and at the end of the program. Resting HRV and measures of psychological outcomes (depression, self-efficacy, decisional balance) were obtained at the start and at the end of the program. Participants of both groups significantly improved their VO2max level, their psychological state and their performance for the 2-back task. Only the participants in the aquaerobics group significantly improved their vagally-mediated HRV and their performance for the Stroop test and the verbal running-span test at the end of the program. Only improvements in cardiac vagal control and in inhibition were shown to be functionally related. These results are discussed in line with the model of neurovisceral integration.