Background: Colorectal cancer (CRC) is the second most prevalent type of cancer in the world. Surgery is the most common therapeutic intervention, and associated with 20–40% reduction in physiological and functional capacity. Postoperative complications occur in up to 50% of patients resulting in higher mortality rates and greater hospital costs. The number and severity of complications is closely related to patients’ preoperative performance status. The aim of this study was to identify the most important preoperative modifiable risk factors that could be part of a multimodal prehabilitation program. Methods: Prospectively collected data of a consecutive series of Dutch CRC patients undergoing colorectal surgery were analyzed. Modifiable risk factors were correlated to the Comprehensive Complication Index (CCI) and compared within two groups: none or mild complications (CCI <20), and severe complications (CCI ≥20). Multivariate logistic regression analysis was done to explore the combined effect of individual risk factors. Results: In this 139 patient cohort, smoking, malnutrition, alcohol consumption, neoadjuvant therapy, higher age, and male sex, were seen more frequently in the severe complications group (CCI ≥20). Patients with severe complications had significantly longer hospital stay (16 vs. 6 days, p < 0.001). The risk for severe complications was increased in patients with ASA score III [adjusted odds ratio (OR) 4.4, 95% CI 1.04–18.6], and hemoglobin level <7 mmol/l (adjusted OR 3.3, 95% CI 1.3–8.2). Compared to having no risk factors, more than one risk factor increased OR of severe complications (crude OR 5.2, 95% CI 1.8–15). Conclusion: This study revealed that the risk of getting severe complications increases with the number of risk factors present preoperatively. Several preoperative patient-related risk factors are modifiable. Multimodal prehabilitation may improve patients’ preoperative status and should be tested in a multicenter randomized controlled trial. With an international consortium (Copenhagen, Montreal, Paris, Eindhoven) we initiated a randomized controlled trial (NTR5947).