To evaluate the risk of all-cause and cardiovascular disease (CVD) mortality associated with each outcome of the NIH obesity treatment algorithm and to examine the effects of cardiorespiratory fitness on the risk of mortality associated with these outcomes. The NIH obesity treatment algorithm was applied to 18,666 men (20 to 64 years of age) from the Aerobics Center Longitudinal Study in Dallas, TX, examined between 1979 and 1995. Risk of all-cause and CVD mortality was assessed using Cox proportional hazards regression. A total of 7029 men (37.7%) met the criteria for needing weight loss treatment [overweight (BMI = 25 to 29.9 kg/m2 or WC > 102 cm) with > or =2 CVD risk factors or obese (BMI > or = 30 kg/m2)]. Mortality surveillance through 1996 identified 435 deaths (151 from CVD) during 191,364 man-years of follow-up. Compared with the normal weight reference group, the hazard ratios (95% confidence interval) for death from all causes were 0.63 (0.45 to 0.88), 1.23 (0.98 to 1.54), 1.05 (0.60 to 1.85), and 1.71 (1.64 to 2.31) for men who were overweight with <2 CVD risk factors, overweight with > or = 2 CVD risk factors, obese with <2 CVD risk factors, and obese with > or =2 CVD risk factors, respectively. Corresponding hazard ratios for CVD mortality were 0.72 (0.38 to 1.37), 1.67 (1.12 to 2.50), 1.69 (0.67 to 4.30), and 3.31 (2.07 to 5.30). Including physical fitness as a covariate significantly attenuated all risk estimates. The NIH obesity treatment algorithm is useful in identifying men at increased risk of premature mortality; however, including an assessment of fitness would help improve risk stratification among all groups of patients.