Cardiorespiratory fitness as an explanation for the obesity paradox warrants further examination. We evaluated independent and joint associations of cardiorespiratory fitness and adiposity with all-cause mortality in 811 middle-aged (age, 53.3 ± 7.2 years) male never smokers without documented cardiopulmonary disease or diabetes from the Veterans Exercise Testing Study (VETS). Cardiorespiratory fitness was quantified in metabolic equivalents (METs) using final treadmill speed and grade achieved on a maximal exercise test. Subjects were grouped for analysis by METs: unfit (lowest third) and fit (upper two-thirds); and by body mass index (kg/m(2)): nonobese (18.5-29.9) and obese (≥30.0). Associations of baseline fitness and adiposity measures with all-cause mortality were determined by Cox proportional hazards analysis adjusted for age, ethnicity, hypertension, hypercholesterolemia, family history of coronary artery disease, and cardiovascular medication use. In multivariate analysis, mortality risk for obese/fit men did not differ significantly from the nonobese/fit reference group. However, compared to the reference group, nonobese and obese unfit men were 2.2 (P = 0.01) and 1.9 (P = 0.03) times more likely to die, respectively. Cardiorespiratory fitness altered the obesity paradox such that mortality risk was lower for both obese and nonobese men who were fit.