Abstract Background: The associations of abdominal skeletal muscle mass index (SMI), visceral and subcutaneous adipose tissue (VAT and SAT, respectively), and mortality among patients with stage I–III colorectal cancer may differ for men and women, but only few studies stratified their data into men and women. We investigated associations of abdominal SMI, VAT, and SAT with overall mortality among men and among women with stage I–III colorectal cancer. Methods: SMI, VAT, and SAT were assessed from abdominal CT images for 1,998 patients with stage I–III colorectal cancer diagnosed between 2006 and 2015. Restricted cubic splines (RCS) were used to investigate associations of SMI, VAT, and SAT with overall mortality. Results: Average age of the participants was 67.9 ± 10.6 years and 58% were men. During a median follow-up of 4.3 years, 546 (27%) patients died. Among men, the association of SMI and mortality was statistically significant in a nonlinear way in the RCS analyses, with lower SMI levels associated with higher mortality. SMI was not associated with mortality among women. SAT was associated with mortality in a nonlinear way for men and for women, with lower SAT levels being associated with higher mortality. VAT was not significantly associated with mortality in men or women. Conclusion: Associations of abdominal skeletal muscle mass with mortality among patients with colorectal cancer were not the same for men and for women. Impact: This study stresses the importance for more attention on sex-related differences in body composition and cancer outcomes.