Background: Body composition has emerged as a potential prognostic factor for outcomes in early-stage CRC. Specifically, muscle mass and quality and visceral fat have been shown to be related to overall survival (OS) and disease-free survival (DFS). The objective of this study was to determine associations of sarcopenia, reduced skeletal muscle radiodensity (SMR) and visceral obesity (VO) with 5-year OS and DFS. Methods: Muscle and visceral fat at the time of diagnosis were quantified in a retrospective cohort of consecutive, early-stage CRC patients (pts), identified from a prospectively collected cancer database. Skeletal muscle area on computed tomography (CT) was measured and normalized by height (m²) in order to compare skeletal muscle index (SMI) between pts. Mean SMR and visceral fat area were measured. All parameters were analyzed using Kaplan-Meier curves and univariate Cox regression. Sarcopenia was defined as SMI < 41 cm²/m² in females and < 43 cm²/m² in males with BMI < 25 kg/m² and < 53 cm²/m² with BMI > 25 kg/m². Reduced SMR was defined as < 41 HU if BMI < 25 kg/m² and < 33 HU if BMI > 25 kg/m². VO was defined as VAT > 160cm² in males and > 80cm² in females. Results: We identified 968 pts with available CTs and anthropometric data. Prevalence of sarcopenia was 44.5% in males and 59.6% in females. Myosteatosis was present in 60.9% of pts. The mean length of follow up was 5.0 years, with 254 patients developing recurrent disease and 351 deaths. Males with sarcopenia and myosteatosis had worse overall survival (HR, 0.69, p = 0.005; HR 0.49, p < 0.001) but no difference in DFS. Presence of VO was not associated with worse OS or DFS. There was no difference in OS for females with sarcopenia or VO, but myosteatosis predicted reduced OS (HR 0.53, p = 0.004). There was no difference in DFS for females by presence of sarcopenia, myosteatosis or VO. Conclusions: Body composition, specifically sarcopenia and myosteatosis, are highly prevalent in CRC pts treated with curative intent, and their presence is associated with reduced OS. Therefore, skeletal muscle mass and radiodensity are important prognostic factors in CRC outcomes, which are easily attained in a clinical setting.