Fatigue is a common and disabling symptom of multiple sclerosis (MS). There is no effective pharmacological treatment for fatigue, although a few reports point towards beneficial effects from physical activity for MS patients suffering from fatigue. We devised a physical activity program for MS patients with fatigue and present the results from our first use of this program, on nine patients from our region. The program consisted of a 20-week series of gradual stretching, resistance and aerobic exercises, adapted to the individual clinical condition of each patient. The results showed significant improvement in cardio-circulatory parameters, as well as a significant decrease in scores on the fatigue scale. The success of this program led patients to ask to continue with it after the trial was finished, and more patients are enrolling in the program, motivated by the good results reported by fellow patients.