To investigate whether greater cardiorespiratory fitness (CRF) is associated with better cognitive function 25 years later. We studied 2,747 participants in the community-based Coronary Artery Risk Development in Young Adults Study of black and white men and women aged 18 to 30 years at recruitment in 1985-1986 (baseline year 0). Symptom-limited maximal treadmill test durations at years 0 and 20 provided measures of CRF. Cognitive tests at year 25 measured verbal memory (Rey Auditory Verbal Learning Test [RAVLT]), psychomotor speed (Digit Symbol Substitution Test [DSST]), and executive function (Stroop Test). Per minute of baseline CRF, the RAVLT was 0.12 words recalled higher (standard error [SE] = 0.03, p < 0.0001), the DSST was 0.92 digits higher (SE = 0.13, p < 0.0001), and the Stroop Test score was 0.52 lower (better performance, SE = 0.11, p < 0.0001), after accounting for race, sex, age, education, and clinical center. Compared with the lowest quartile of CRF, each cognitive test was 21% to 34% of an SD better in the highest CRF quartile. Further adjustment for lifestyle and clinical measures attenuated coefficients for RAVLT and DSST slightly, while the coefficient predicting the Stroop Test lost more than half its value (p = 0.07). Analysis in the subset of 1,957 participants who also completed the year-20 treadmill test showed that 20-year change in CRF was positively associated only with DSST (p < 0.001). Better verbal memory and faster psychomotor speed at ages 43 to 55 years were clearly associated with better CRF 25 years earlier.