The aim of this study was to investigate the effects of different protocols of moderate intensity intermittent hypoxic training in patients who had recovered from COVID-19 on quality of life (QoL) and mental health. The sample of this clinical trial-controlled double-blind study consisted of 67 participants aged 30–69 years, who were organized randomly according to Normoxia, Hypoxia, Hypoxia Recovery or Control Group. Eight weeks of cycle ergometer training were performed with a frequency of three training sessions per week in normoxic or hypoxic conditions (with or without hypoxic recovery). Health-related QoL and Mental Health Status were evaluated by 12-Item Short Form Survey and Depression Anxiety and Stress Scale instruments, respectively. All training groups improved the QoL’s physical dimensions (Baseline–Post: Normoxia Group 42.1 (11.0)–48.7 (7.0), Hypoxia Group 46.9 (11.8)–53.5 (6.6) and Hypoxia Recovery Group 45.8 (9.2)–51.1 (5.3)) and mental dimensions (Baseline–Post: Normoxia Group 48.8 (7.9)–54.6 (4.6), Hypoxia Group 45.2 (7.7)–53.2 (3.8) and Hypoxia Recovery Group 46.5 (9.7)–52.0 (9.9)). Regarding mental health outcomes, all training groups decreased depressive symptoms (66.7% Normoxia, 31.2% Hypoxia Recovery and 31% Hypoxia groups), anxiety symptoms (46.5% Normoxia, 45.9% Hypoxia Recovery and 39.5% in the Hypoxia groups) and stress symptoms (40.6% Normoxia, 36.3% Hypoxia Recovery and 22.1% Hypoxia groups). Significant statistical difference was not found between groups. Normoxic and hypoxic training showed a similar effect on QoL and the mental health of Brazilian adults who had recovered from COVID-19.