Abnormal levels of pyruvate and lactate were reported in multiple sclerosis (MS). We studied the response of markers of mitochondrial function to rehabilitation in relation to type, intensity and endurance performance in severely disabled MS patients. Forty-six progressive MS patients were randomized to receive 12 walking sessions of robot-assisted gait training (RAGT, n = 23) or conventional overground therapy (CT, n = 23). Ten healthy subjects were also studied. Blood samples were collected to determine lactate, pyruvate, and glutathione levels and lactate/pyruvate ratio pre–post rehabilitation. In vivo muscle metabolism and endurance walking capacity were assessed by resting muscle oxygen consumption (rmVO2) using near-infrared spectroscopy and by six-minute walking distance (6MWD), respectively. The levels of mitochondrial biomarkers and rmVO2, altered at baseline with respect to healthy subjects, improved after rehabilitation in the whole population. In the two groups, an enhanced response was observed after RAGT compared to CT for lactate (p = 0.012), glutathione (<0.001), lactate/pyruvate ratio (p = 0.08) and rmVO2 (p = 0.07). Metabolic biomarkers and 6MWD improvements were exclusively correlated with a training speed markedly below individual gait speed. In severely disabled MS patients, rehabilitation rebalanced altered serum metabolic and muscle parameters, with RAGT being more effective than CT. A determinable slow training speed was associated with better metabolic and functional recovery. Trial Registration: ClinicalTrials.gov NCT02421731.