Colorectal cancer (CRC) survivors need evidence-based guidelines pertaining to post-treatment body composition, which could benefit health-related quality of life (HRQoL). We aimed to describe the course of several body composition measures, and to assess longitudinal associations of these measures with HRQoL, fatigue and chemotherapy-induced peripheral neuropathy (CIPN). In a prospective cohort among stage I–III CRC survivors (n = 459), five repeated home visits from diagnosis up to 24 months post-treatment were executed. Body mass index (BMI), waist circumference and fat percentage were assessed as measures of adiposity, and muscle arm circumference and handgrip strength as measures of muscle mass and function. We applied linear mixed-models to describe changes in body composition over time and to analyze overall longitudinal associations. Of included participants, 44% was overweight and 31% was obese at diagnosis. All body composition measures followed similar trends, decreasing from diagnosis to 6 weeks and then increasing up to 24 months post-treatment. In confounder-adjusted mixed models, increases in adipose tissue and muscle function were longitudinally associated with better HRQoL and less fatigue, regardless of pre-treatment body composition. With regards to improving HRQoL, decreasing fatigue and CIPN, clinical practice should also focus on restoring body tissues after CRC treatment. Trial registration: NTR7099.