Background: Physical activity might attenuate inflammation and neurodegeneration in multiple sclerosis (MS). Erythropoietin, which is produced upon exposure to hypoxia, is thought to act as a neuroprotective agent in MS. Therefore, we studied the effects of intermittent hypoxic training on activity energy expenditure, maximal workload, serum erythropoietin, and immunophenotype focusing on regulatory and IL-17A-producing T cells. Methods: We assigned 34 relapsing-remitting MS patients within a randomized, single blind, parallel-group study to either normoxic (NO) or hypoxic (HO) treadmill training, both 3 times/week for 1 h over 4 weeks (Clinicaltrials.gov identifier: NCT02509897). Before and after training, activity energy expenditure (metabolic chamber), maximal workload (incremental treadmill test), walking ability, depressive symptoms (Beck Depression Inventory I), serum erythropoietin concentrations, and immunophenotype of peripheral blood mononuclear cells (PBMCs) were assessed. Results: Energy expenditure did not change due to training in both groups, but was rather fueled by fat than by carbohydrate oxidation after HO training (P = 0.002). Maximal workload increased by 40 Watt and 42 Watt in the NO and HO group, respectively (both P < 0.0001). Distance patients walked in 6 min increased by 25 m and 27 m in the NO and HO group, respectively (NO P = 0.02; HO P = 0.01). Beck Depression Inventory score markedly decreased in both groups (NO P = 0.03; HO P = 0.0003). NO training shifted Treg subpopulations by increasing and decreasing the frequency of CD39(+) and CD31(+) Tregs, respectively, and decreased IL-17A-producing CD4(+) cells. HO training provoked none of these immunological changes. Erythropoietin concentrations were within normal range and did not significantly change in either group. Conclusion: 4 weeks of moderate treadmill training had considerable effects on fitness level and mood in MS patients, both under normoxic and hypoxic conditions. Additionally, NO training improved Th17/Treg profile and HO training improved fatty acid oxidation during exercise. These effects could not be attributed to an increase of erythropoietin.