Background: To what extent sex-related differences in cardiorespiratory fitness (CRF) impact postoperative patient mortality and corresponding implications for surgical risk stratification remains to be established. Methods: To examine this, we recruited 640 patients (366 males vs. 274 females) who underwent cardiopulmonary exercise testing prior to elective colorectal surgery. Patients were defined high risk if peak oxygen uptake was <14.3 mL kg⁻¹ min⁻¹ and ventilatory equivalent for carbon dioxide at ‘anaerobic threshold’ >34. Between-sex CRF and mortality was assessed, and sex-specific CRF thresholds predictive of mortality was calculated. Results: Seventeen percent of deaths were attributed to sub-threshold CRF, which was higher than established risk factors for cardiovascular disease (CVD). The group (independent of sex) exhibited a 5-fold higher mortality (high vs. low risk patients hazard ratio = 4.80, 95% confidence interval 2.73–8.45, p < 0.001). Females exhibited 39% lower CRF (p < 0.001) with more classified high risk than males (36 vs. 23%, p = 0.001), yet mortality was not different (p = 0.544). Upon reformulation of sex-specific CRF thresholds, lower cut-offs for mortality were observed in females, and consequently, fewer (20%) were stratified with sub-threshold CRF compared to the original 36% (p < 0.001). Conclusions: Low CRF accounted for more deaths than traditional CVD risk factors, and when CRF was considered relative to sex, the disproportionate number of females stratified unfit was corrected. These findings support clinical consideration of ‘sex-specific’ CRF thresholds to better inform postoperative mortality and improve surgical risk stratification.