Background: The aim of this nationwide cohort study was to examine the course of symptoms and trajectories of health-related quality of life (HR-QoL) and psychological distress during follow-up and to identify vulnerable patients. Methods: Patients with pathological stage I–III colorectal cancer (CRC) between 2013 and 2018 were included. Baseline characteristics were collected from the Netherlands Cancer Registry, and patients completed the European Organisation for Research and Treatment of Cancer QLQ-C30/CR29, Hospital Anxiety and Depression Scale and low anterior resection syndrome (LARS) questionnaires at the baseline and subsequently at 3, 6, 12, 18 and 24 months. Latent class growth and multinomial logistic regression analyses were performed to outline 24-month trajectories in HR-QoL and distress and to identify predictive factors. Results:: A total of 1535 patients with colon cancer or rectal cancer were included. Trajectory analysis of HR-QoL identified three patient classes: high HR-QoL (62.7%), improving HR-QoL (29.0%) and low HR-QoL (8.3%). The following patient groups were identified with having low distress (64.0%), moderate distress (26.9%) and high distress (9.1%). Around 13% of the total cohort had either persistent low HR-QoL or high psychological distress throughout follow-up. Patients belonging to this vulnerable group were significantly more likely to be female, to be younger aged, to have lower education, to have disease stage II–III or to have major LARS. Conclusions: Although most patients treated for stage I–III CRC fared well, a small but significant proportion of around 13% did not recover during follow-up and reported low HR-QoL and/or high psychological distress levels throughout. This study's findings should be taken into account when organising and selecting patients for tailored follow-up.