Background: the post-COVID-19 condition is a novel condition for which guidelines recommend supervised exercise, but evidence guiding safe and effective interventions is limited. The aim of this study was to investigate the effects of a tailored exercise program (EXER-COVID 5 trial) on cardiorespiratory fitness, muscle strength, long COVID symptoms, cognitive performance, quality of life, depression, and psychological distress. Methods: this crossover study included 100 participants with post-COVID-19 conditions (mean 8 age 48 years; 68% women) at a single center in Spain from March 1, 2021, to September 30, 2022. Participants were randomized 1:1 to 6 weeks of muscle power resistance training (PRT) followed by 6 weeks of usual care (Group 1 [AB], n=50) or 6 weeks of usual care followed by 6 weeks of muscle power RT (Group 2 [BA], n=50). Results: the intervention significantly improved the peak VO2 by 2.10 mL/kg/min [95% CI 1.25 to 2.94], P<0.001. Per-protocol analyses revealed similar results (2.40 mL/kg/min [95% CI 1.56 to 3.25]), P<0.001. No carry-over or period effects were detected. After power PRT, strength (1RM) was improved for pectoral press, bilateral leg-press, knee extension, and back press (P<0.001). Significant decreases were found in psychological distress scores (P<0.001). The intervention also improved quality of life (P=0.041), cognitive capabilities (P=0.014) and cognitive performance (P=0.036). Furthermore, the exercise program reduced seven of the 22 long-COVID symptoms, including weakness (RR= 0.75) dyspnea (RR= 0.56), hearing loss/tinnitus (RR= 0.86), change in appetite (RR= 0.84), memory loss (RR= 0.84), stress (RR= 0.80) and apathy/depression (RR= 0.80), (all Ps<0.05). Conclusions: a supervised 6-week PRT intervention program safely improved cardiorespiratory fitness, strength, and mental health in participants with post-COVID-19 conditions. These findings provide clinicians with evidence to support exercise as standard co-therapy and warrant further study.