Abstract Purpose Post-acute sequelae of COVID-19 (PASC) affect approximately 10% of convalescent patients. The spectrum of symptoms is broad and heterogeneous with fatigue being the most often reported sequela. Easily accessible blood biomarkers to determine PASC severity are lacking. Thus, our study aimed to correlate immune phenotypes with PASC across the severity spectrum of COVID-19. Methods A total of 176 originally immunonaïve, convalescent COVID-19 patients from a prospective cohort during the first pandemic phase were stratified by initial disease severity and underwent clinical, psychosocial, and immune phenotyping around 10 weeks after first COVID-19 symptoms. COVID-19-associated fatigue dynamics were assessed and related to clinical and immune phenotypes. Results Fatigue and severe fatigue were commonly reported irrespective of initial COVID-19 severity or organ-specific PASC. A clinically relevant increase in fatigue severity after COVID-19 was detected in all groups. Neutralizing antibody titers were higher in patients with severe acute disease, but no association was found between antibody titers and PASC. While absolute peripheral blood immune cell counts in originally immunonaïve PASC patients did not differ from unexposed controls, peripheral CD3+CD4+ T cell counts were independently correlated with fatigue severity across all strata in multivariable analysis. Conclusions Patients were at similar risk of self-reported PASC irrespective of initial disease severity. The independent correlation between fatigue severity and blood T cell phenotypes indicates a possible role of CD4+ T cells in the pathogenesis of post-COVID-19 fatigue, which might serve as a blood biomarker.