Fifty-four multiple sclerosis (MS) patients were randomly assigned to exercise (EX) or nonexercise (NEX) groups. Before and after 15 weeks of aerobic training, aspects of fitness including maximal aerobic capacity (VO2max), isometric strength, body composition, and blood lipids were measured. Daily activities, mood, fatigue, and disease status were measured by the Profile of Mood States (POMS), Sickness Impact Profile (SIP), Fatigue Severity Scale (FSS), and neurological examination. Training consisted of 3 x 40-minute sessions per week of combined arm and leg ergometry. Expanded Disability Status Scale (EDSS) scores were unchanged, except for improved bowel and bladder function in the EX group. Compared with baseline, the EX group demonstrated significant increases in VO2max, upper and lower extremity strength, and significant decreases in skinfolds, triglyceride, and very-low-density lipoprotein (VLDL). For the EX group, POMS depression and anger scores were significantly reduced at weeks 5 and 10, and fatigue was reduced at week 10. The EX group improved significantly on all components of the physical dimension of the SIP and showed significant improvements for social interaction, emotional behavior, home management, total SIP score, and recreation and past times. No changes were observed for EX or NEX groups on the FSS. Exercise training resulted in improved fitness and had a positive impact on factors related to quality of life.