Previous studies have demonstrated that cardiorespiratory fitness is a strong marker of cardiovascular health. Machine learning (ML) can enhance the prediction of outcomes through classification techniques that classify the data into predetermined categories. The aim of the analysis is to compare the prediction of 10 years of all-cause mortality (ACM) using statistical logistic regression (LR) and ML approaches in a cohort of patients who underwent exercise stress testing. We included 34,212 patients (55% males, mean age 54 ± 13 years) free of coronary artery disease or heart failure who underwent exercise treadmill stress testing between 1991 and 2009 and had complete 10-year follow-up. The primary outcome of this analysis was ACM at 10 years. The probability of 10-years ACM was calculated using statistical LR and ML, and the accuracy of these methods was calculated and compared. A total of 3,921 patients died at 10 years. Using statistical LR, the sensitivity to predict ACM was 44.9% (95% confidence interval [CI] 43.3% to 46.5%), whereas the specificity was 93.4% (95% CI 93.1% to 93.7%). The sensitivity of ML to predict ACM was 87.4% (95% CI 86.3% to 88.4%), whereas the specificity was 97.2% (95% CI 97.0% to 97.4%). The ML approach was associated with improved model discrimination (area under the curve for ML [0.923 (95% CI 0.917 to 0.928)]) compared with statistical LR (0.836 [95% CI 0.829 to 0.846], p < 0.0001). In conclusion, our analysis demonstrates that ML provides better accuracy and discrimination of the prediction of ACM among patients undergoing stress testing.