Introduction: Physical activity and sleep are closely related behaviors with suggested synergistic influence on cardiovascular health. Physical activity potentially modifies associations between sleep and mortality. Our aim was to study the interrelationships between sleep, leisure-time physical activity (LTPA), a history of sports, and mortality. Methods: A prospective cohort of former elite male athletes (n = 1,028), and age- and region-matched nonathlete men (n = 610) completed a health questionnaire in 1985. Their mortality was followed up until December 31, 2011. Analyses included Cox proportional hazards models with sleep duration and sleep quality as main predictors of all-cause and cardiovascular disease (CVD) mortality. Results: Sleep duration or sleep quality were not independently associated with mortality after controlling for socioeconomic and lifestyle factors. The interaction between sleep duration and LTPA was significant, with higher risk of all-cause and CVD mortality if sleeping 6 hours or less and not achieving 450 metabolic equivalent minutes LTPA weekly, as compared with sleeping 6.5–8.5 hours and achieving 450 metabolic equivalent minutes of LTPA. Also, the relative excess risk due to interaction between short sleep and low LTPA was significant for CVD mortality. Discussion: Significant interactions between sleep duration and LTPA with regard to mortality were observed. In particular, short sleep and low LTPA jointly predicted all-cause and CVD mortality irrespective of a history of sports. Findings suggest important synergistic associations of short sleep and low LTPA with CVD mortality risk.