Purpose: The current study determined the prevalence of severe fatigue in adolescent and young adult (AYA) cancer patients (aged 18–35 years at diagnosis) consulting a multidisciplinary AYA team in comparison with gender- and age-matched population-based controls. In addition, impact of severe fatigue on quality of life and correlates of fatigue severity were examined. Methods: AYAs with cancer (n = 83) completed questionnaires including the Checklist Individual Strength (CIS-fatigue), Quality of Life (QoL)-Cancer Survivor, Hospital Anxiety and Depression Scale (reflecting psychological distress), and the Cancer Worry Scale (reflecting fear of cancer recurrence or progression). Results: The vast majority of participants had been treated with chemotherapy (87%) and had no active treatment at the time of participation (73.5%). Prevalence of severe fatigue (CIS-fatigue score ≥35) in AYAs with cancer (48%, n = 40/83) was significantly higher in comparison with matched population-based controls (20%, n = 49/249; p < .001). Severely fatigued AYAs with cancer reported lower QoL compared to non-severely fatigued AYAs with cancer (p < .05). Female gender, being unemployed, higher disease stage (III–IV) at diagnosis, receiving active treatment at the time of study participation, being treated with palliative intent, having had radiotherapy, higher fear of recurrence or progression, and higher psychological distress were significantly correlated with fatigue severity (p < .05). Conclusions: Severe fatigue based on a validated cut-off score was highly prevalent in this group of AYAs with cancer. QoL is significantly affected by severe fatigue, stressing the importance of detection and management of this symptom in those patients affected by a life-changing diagnosis of cancer in late adolescence or young adulthood.