Cognitive impairments are commonly observed in patients with multiple sclerosis and are associated with lower levels of quality of life. No consensus has been reached on how to tackle effectively cognitive decline in this clinical population non-pharmacologically. This exploratory case-control study aims to investigate the effectiveness of a hypothesis-based cognitive training designed to target multiple domains by promoting the synchronous co-activation of different brain areas and thereby improve cognition and induce changes in functional connectivity in patients with relapsing-remitting multiple sclerosis. Forty-five patients (36 females and 9 males, mean age 44.62 ± 8.80 years) with clinically stable relapsing-remitting multiple sclerosis were assigned to either a standard cognitive training or to control groups (sham training and non-active control). The standard training included twenty sessions of computerized exercises involving various cognitive functions supported by distinct brain networks. The sham training was a modified version of the standard training that comprised the same exercises and number of sessions but with increased processing speed load. The non-active control group received no cognitive training. All patients underwent comprehensive neuropsychological and magnetic resonance imaging assessments at baseline and after 5 weeks. Cognitive and resting-state magnetic resonance imaging data were analyzed using repeated measures models. At reassessment, the standard training group showed significant cognitive improvements compared to both control groups in memory tasks not specifically targeted by the training: the Buschke Selective Reminding Test and the Semantic Fluency test. The standard training group showed reductions in functional connectivity of the salience network, in the anterior cingulate cortex, associated with improvements on the Buschke Selective Reminding Test. No changes were observed in the sham training group. These findings suggest that multi-domain training that stimulates multiple brain areas synchronously may improve cognition in people with relapsing-remitting multiple sclerosis if sufficient time to process training material is allowed. The associated reduction in functional connectivity of the salience network suggests that training-induced neuroplastic functional reorganization may be the mechanism supporting performance gains. This study was approved by the Regional Ethics Committee of Yorkshire and Humber (approval No. 12/YH/0474) on November 20, 2013.