Cardiorespiratory fitness (CRF) is inversely associated with atherosclerotic cardiovascular disease (ASCVD) risk. It is unclear whether the prognostic value of CRF differs by baseline estimated ASCVD risk. We studied a retrospective cohort of patients without known heart failure or myocardial infarction (MI) who underwent treadmill stress testing. CRF was measured by metabolic equivalents of task (METs) and ASCVD risk was calculated using the Pooled Cohorts Equations. Multivariable-adjusted Cox regressions analyses examined the association between METs and incident all-cause mortality and MI outcomes stratified by baseline ASCVD risk. The C-index evaluated risk discrimination while net reclassification improvement evaluated reclassification with CRF added to the ASCVD risk score. Our study population consisted of 57,999 patients of mean age 53 (13) years, 49% women, 64% white, 29% black. Over a median follow-up 11 years (interquartile range 8 to 14 years) there were 6,670 (11%) deaths, while there were 1,757 (3.0%) MIs over a median follow-up of 6 years (interquartile range 3 to 8 years). Among patients with ASCVD risk ≥20%, those with METs ≥12 had a 77% lower risk of all-cause mortality (Hazard ratio 0.23 95% confidence interval = 0.20, 0.27) and 67% lower risk of MI (Hazard ratio 0.33 95% confidence interval = 0.24, 0.46) compared to METs <6. Similar results were obtained for those with ASCVD risk <5%. Addition of METs to ASCVD risk score improved the C-statistic from 0.778 to 0.798 for all-cause mortality and 0.726 to 0.733 for MI (both p <0.001). Addition of METs to ASCVD risk score significantly reclassified risk of all-cause mortality (p <0.001) but not MI (p = 0.052). In conclusion, CRF is inversely associated with risk of all-cause mortality and MI at all levels of ASCVD risk, and provides incremental risk discrimination and reclassification beyond the ASCVD risk score.