Objective: Physical exercise has been linked to higher cognitive functioning and enhanced brain plasticity in aging humans. The most consistent positive effects have been reported for executive functions associated with frontal brain regions. In rodents, however, running has been shown to induce functional and structural changes in the hippocampus, a brain region known to be important for memory. It is still a matter of debate which cognitive functions are susceptible to exercise and whether an increase in cardiovascular fitness is beneficial for cognitive functioning. Moreover, little is known about the impact of exercise on cognition in middle-aged humans. Method: Sixty-eight sedentary men and women between 40 and 56 years of age were randomly assigned to one of two training programs: aerobic endurance training (cycling) or nonendurance training (stretching/coordination). Both groups exercised twice a week for six months. Additionally, a sedentary control group was tested. At baseline and after six months, episodic memory, perceptual speed, executive functions, and spatial reasoning were assessed with standardized psychometric tests, and all participants underwent a cardiovascular fitness test. Results: Significant improvements in memory were observed in both the cycling and the stretching/coordination group as compared with the sedentary control group. The improvement in episodic memory correlated positively with the increase in cardiovascular fitness. The stretching/coordination training particularly improved selective attention as compared with the cycling training. Conclusions: The results suggest that cardiovascular fitness has beneficial effects even in high-functioning middle-aged participants, but that these benefits are very specific to memory functions rather than a wider range of cognitive functions.