Background Depression and fatigue are commonly observed sequelae following viral diseases such as COVID-19. Identifying symptom constellations that differentially classify post-COVID depression and fatigue may be helpful to individualize treatment strategies. Here, we investigated whether self-reported post-COVID depression and post-COVID fatigue are associated with the same or different symptom constellations. Methods To address this question, we used data from COVIDOM, a population-based cohort study conducted as part of the NAPKON-POP platform. Data were collected in three different German regions (Kiel, Berlin, Würzburg). We analyzed data from textgreater2000 individuals at least six months past a PCR-confirmed COVID-19 disease, using elastic net regression and cluster analysis. The regression model was developed in the Kiel data set, and externally validated using data sets from Berlin and Würzburg. Results Our results revealed that post-COVID depression and fatigue are associated with overlapping symptom constellations consisting of difficulties with daily activities, perceived health-related quality of life, chronic exhaustion, unrestful sleep, and impaired concentration. Confirming the overlap in symptom constellations, a follow-up cluster analysis could categorize individuals as scoring high or low on depression and fatigue but could not differentiate between both dimensions. Limitations The data presented are cross-sectional, consisting primarily of self-reported questionnaire or medical records rather than biometric data. Conclusions In summary, our results suggest a strong link between post-COVID depression and fatigue, highlighting the need for integrative treatment approaches.