Background Few studies have examined how various lifestyle factors in midlife predict longevity, and none of these studies have examined the impact of physical fitness. The present study aimed to examine longevity in relation to smoking, overweight and physical fitness. Methods We prospectively studied longevity (defined as reaching at least 85 years of age) in relation to smoking status, body mass index and physical fitness in 821 healthy men between 51 and 59 years of age. Of these, 369 were smokers, 320 were overweight, and 31 were obese. The associations were adjusted for age, systolic blood pressure and cholesterol level, using multivariate logistic regression analysis. Deaths were registered until the 31st of December, 2006. Physical fitness was measured as the total work performed in a maximal exercise tolerance bicycle test. Results 252 men survived to the age of 85 years (30.7%). Smoking status was significantly and independently related to longevity; 37.2% of the non-smokers survived to the age of 85, and 22.8% of the smokers. Among non-smokers, overweight and physical fitness were significantly and independently related to longevity after adjustment for age, blood pressure and cholesterol level, but not among smokers. Among non-smokers with high physical fitness, 48.8% reached the age of 85 years, compared to 27.9% among non-smokers with low physical fitness. Conclusion Lifestyle variables appear to be strong and independent predictors of longevity in initially healthy middle-aged men. The probability of longevity may be a useful concept when informing the general public about the benefits of a healthy lifestyle.