Background: In cancer patients with a poor prognosis, low skeletal muscle radiographic density is associated with higher mortality. Whether this association also holds for early-stage cancer is not very clear. We aimed to study the association between skeletal muscle density and overall mortality among early-stage (stage I–III) colorectal cancer (CRC) patients. Furthermore, we investigated the association between skeletal muscle density and both CRC-specific mortality and disease-free survival in a subset of the study population. Methods: Skeletal muscle density was assessed in 1681 early-stage CRC patients, diagnosed between 2006 and 2015, using pre-operative computed tomography images. Adjusted Cox proportional hazard models were used to evaluate the association between muscle density and overall mortality, CRC-specific mortality and disease-free survival. Results: The median follow-up time was 48 months (range 0–119 months). Low muscle density was detected in 39% of CRC patients. Low muscle density was significantly associated with higher mortality (low vs. normal: adjusted HR 1.91, 95% CI 1.53–2.38). After stratification for comorbidities, the association was highest in patients with ≥ 2 comorbidities (HR 2.11, 95% CI 1.55–2.87). Furthermore, low skeletal muscle density was significantly associated with poorer disease-free survival (HR 1.68, 95% CI 1.14–2.47), but not with CRC-specific mortality (HR 1.68, 95% CI 0.89–3.17) in a subset of the study population. Conclusion: In early-stage CRC patients, low muscle density was significantly associated with higher overall mortality, and worse disease-free survival.