1-methyl-4-phenyl-1,2,3,6-tetrahydropyridine (MPTP) induces permanent neurochemical and functional deficits. Following the administration of either two or four injections of the dopamine neurotoxin, MPTP, at a dose of 40 mg/kg, C57/BL6 mice were given access to running-wheels (30-min sessions, four times/week, Monday–Thursday) and treatment with the treated yeast, Milmed® (four times/week, Monday–Thursday), or simply running-wheel exercise by itself, over ten weeks. It was observed that the combination of physical exercise and Milmed® treatment, the MPTP + Exercise + Yeast (MC) group [MPTP + Exercise + Milmed® (MC)], restored spontaneous motor activity markedly by test day 10, restored completely subthreshold L-Dopa-induced activity, and dopamine concentration to 76% of control values, in the condition wherein two administrations of MPTP (2 × 40 mg/kg) were given prior to initiation of exercise and/or Milmed® treatment. Physical exercise by itself, MPTP + Exercise (MC) group, attenuated these deficits only partially. Administration of MPTP four times (i.e., 40 mg/kg, s.c., once weekly over four weeks for a total of 160 mg/kg, MPTP + Exercise + Yeast (MC) group [MPTP + Exercise + Milmed® (SC)] and MPTP + Exercise (SC), induced a lesioning effect that was far too severe for either exercise alone or the exercise + Milmed® combination to ameliorate. Nevertheless, these findings indicate a powerful effect of physical exercise reinforced by Milmed® treatment in restoring MPTP-induced deficits of motor function and dopamine neurochemistry in mice.