(1) Background: prehabilitation programs improve postoperative outcomes in vulnerable patients undergoing major surgery. However, current screening tools such as the Malnutrition Universal Screening Tool (MUST) may lack the sensitivity needed to identify those who would benefit most. Muscle quality assessed by Computed Tomography (CT), specifically muscle radiodensity in Hounsfield Units (HU), has emerged as a promising alternative for risk stratification; (2) Objective: to evaluate the prognostic performance of CT-derived muscle radiodensity in predicting adverse postoperative outcomes in colorectal cancer patients, and to compare it with the performance of the MUST score; (3) Methods: this single-center cross-sectional study included 201 patients with non-metastatic colon cancer undergoing elective laparoscopic resection. Patients were stratified by enrollment in a multimodal prehabilitation program (ERAS vs. non-ERAS). Nutritional status was assessed using MUST, SARC-F and GLIM criteria. CT scans at the L3 level were analyzed using automated segmentation to extract muscle area and radiodensity. Postoperative complications and hospital stay were compared across nutritional screening tools and CT-derived metrics; (4) Results: MUST shows limited sensitivity (<27%) for predicting complications and prolonged hospitalization. In contrast, CT-derived muscle radiodensity demonstrates higher discriminative power (AUC 0.62–0.69), especially using a 37 HU threshold. In the non-ERAS group, patients with HU ≤ 37 had significantly more complications (33% vs. 15%, p = 0.036), longer surgeries, and more severe events (Clavien-Dindo ≥ 3); (5) Conclusion: opportunistic CT-based assessment of muscle radiodensity outperforms traditional screening tools in identifying patients at risk of poor postoperative outcomes, and may enhance patient selection for prehabilitation strategies like ERAS program. Funding: none.