A high cardiorespiratory fitness (CRF) level is recommended to promote healthy aging. However, the association between CRF and very-long-term prognosis is unclear, and reverse causation may bias results in studies with shorter follow-up. This study investigated the association between CRF and mortality in middle-aged, employed men free of cardiovascular disease (CVD). Participants from the Copenhagen Male Study, established in 1970 to 1971, were included and stratified into 4 age-adjusted maximal oxygen consumption (Vo2max) categories: below the lower limit of normal (lowest 5%); low normal (45%); high normal (45%); and above the upper limit of normal (top 5%). Vo2max was estimated by using a bicycle ergometer. Multivariable restricted mean survival time models were performed for all-cause and cardiovascular mortality using Danish national registers. A total of 5,107 men with a mean age of 48.8 ± 5.4 years were included in the study. During the 46 years of follow-up, 4,700 (92%) men died; 2,149 (42.1%) of the men died of CVD. Compared with below the lower limit of normal CRF, low normal CRF was associated with 2.1 years (95% confidence interval [CI]: 0.7 to 3.4; p = 0.002), high normal with 2.9 years (95% CI: 1.5 to 4.2; p < 0.001), and above upper limit of normal with 4.9 years (95% CI: 3.1 to 6.7; p < 0.001) longer mean life expectancy. Each unit increase in Vo2max was associated with a 45-day (95% CI: 30 to 61; p < 0.001) increase in longevity. Estimates for cardiovascular mortality were similar to all-cause mortality. Results were essentially unchanged when excluding individuals who died within the first 10 years of follow-up, suggesting a minimal role of reverse causation. CRF was significantly related to longevity over the course of 4 decades in middle-aged, employed men free of CVD. The benefits of higher midlife CRF extend well into the later part of life.