The objective of the study was to treat fatigue in patients with multiple sclerosis (MS) by a neurocognitive rehabilitation program aimed at improving motor planning by using motor imagery (MI). Twenty patients with clinically definite MS complaining of fatigue were treated for five weeks with exercises of neurocognitive rehabilitation twice a week. Patients were evaluated by Fatigue Severity Scale (FSS), Modified Fatigue Impact Scale (MFIS), MSQoL54, Expanded Disability Status Scale (EDSS), and MS Functional Composite (MSFC). After treatment, a decrease in fatigue was detected with both FSS (P = 0.0001) and MFIS (P = 0.0001). MSFC (P = 0.035) and MSQoL54 (P = 0.002) scores improved compared to baseline. At six-month followup, the improvement was confirmed for fatigue (FSS, P = 0.0001; MFIS P = 0.01) and for the physical subscale of MSQoL54 (P = 0.049). No differences in disability scales were found. These results show that neurocognitive rehabilitation, based on MI, could be a strategy to treat fatigue in MS patients.