OBJECTIVE: Post-COVID syndrome involves prolonged symptoms with multi-system and functional impairment lasting at least 12 weeks after acute COVID-19. We aimed to determine the efficacy of exercise-based rehabilitation interventions, either face-to-face or remote, compared to usual care in individuals experiencing Post-COVID syndrome following a hospitalisation of acute COVID-19. DESIGN: This single-blind randomised controlled trial compared two COVID exercise-based rehabilitation interventions (face-to-face or remote) to usual care in participants with Post-COVID syndrome following a hospitalisation. The interventions were either a face-to-face or remote eight-week program of individually prescribed exercise and education. The primary outcome was the change in Incremental Shuttle Walking Test (ISWT) following eight weeks of intervention (either face-to-face or remote) compared to usual care. Other secondary outcomes were measured including health related quality of life (HRQoL), and exploratory outcomes included lymphocyte immunotyping. RESULTS: 181 participants (55% male, mean [sd] age 59 [12] years, length of hospital stay 12 [19] days) were randomised. There was an improvement in the ISWT distance following face-to-face rehabilitation (mean 52 [95% CI 19 to 85]m, p=0·002) and remote rehabilitation (mean 34 [95% CI 1 to 66]m, p=0·047) compared to usual care alone. There were no differences between groups for HRQoL of self-reported symptoms. Analysis of immune markers revealed significant increases in naïve and memory CD8+ T cells following face-to-face rehabilitation versus usual care alone (p<0·001, n=31). CONCLUSION: Exercise-based rehabilitation improved short-term exercise capacity in Post-COVID syndrome following an acute hospitalisation and showed potential for beneficial immunomodulatory effects.