A few months of physical exercise have been shown to increase cognition and to modulate brain functions in previously sedentary, mainly older adults. However, whether the preservation of newly gained cognitive capacities requires an active maintenance of the achieved fitness level during the intervention is not yet known. The aim of the present study was to test whether cardiovascular fitness one year after an exercise intervention was linked to cognitive variables. Twenty-five healthy participants (42-57 years of age) took part in a follow-up assessment one year after the end of a supervised exercise intervention. Measurements included a cardiovascular fitness test, psychometric tests of verbal learning and memory and selective attention as well as questionnaires assessing physical activity and self-efficacy beliefs. Recognition scores of participants with higher cardiovascular fitness at follow-up did not change significantly during the follow-up period; however, the scores of participants with lower cardiovascular fitness decreased. One year after the end of the physical training intervention, previously sedentary participants spent more hours exercising than prior to the intervention. The time participants spent exercising correlated with their self-efficacy beliefs. These results demonstrate a direct link between verbal learning and cardiovascular fitness and show that positive effects of physical interventions on learning and memory do need an active maintenance of cardiovascular fitness.