This study examined the effects of two short physical training programs on various parameters of heart rate variability (HRV) and on executive performance in older people. Twenty-four sedentary men and women aged 65-78 years were randomly assigned to an aerobic exercise program or a stretching program three times a week for 12 weeks. Resting HRV was measured in time and frequency domains in each participant before and after the 12-week programs. Executive performance was measured with the Wisconsin card sorting test (WCST). Significant group-session interactions emerged for the standard deviation of normal beat-to-beat (R-R) intervals, the root-mean-square of successive R-R, and high frequency power. Only the aerobic training group increased vagal-mediated HRV parameters. Moreover, only the participants in the aerobic training group improved their performance on the WCST. These results highlight the role of aerobic exercise as an important cardiac and brain protective factor, and suggest a direct link between exercise, HRV, and cognition in the aged population.