Multiple sclerosis (MS) is an autoimmune inflammatory demyelinating and neurodegenerative disorder of the central nervous system characterized by multifocal white matter brain lesions leading to alterations in connectivity at the subcortical and cortical level. Graph theory, in combination with neuroimaging techniques, has been recently developed into a powerful tool to assess the large-scale structure of brain functional connectivity. Considering the structural damage present in the brain of MS patients, we hypothesized that the topological properties of resting-state functional networks of early MS patients would be re-arranged in order to limit the impact of disease expression. A standardized dual task (Paced Auditory Serial Addition Task simultaneously performed with a paper and pencil task) was administered to study the interactions between behavioral performance and functional network re-organization. We studied a group of 16 early MS patients (35.3 ± 8.3 years, 11 females) and 20 healthy controls (29.9 ± 7.0 years, 10 females) and found that brain resting-state networks of the MS patients displayed increased network modularity, i.e. diminished functional integration between separate functional modules. Modularity correlated negatively with dual task performance in the MS patients. Our results shed light on how localized anatomical connectivity damage can globally impact brain functional connectivity and how these alterations can impair behavioral performance. Finally, given the early stage of the MS patients included in this study, network modularity could be considered a promising biomarker for detection of earliest-stage brain network reorganization, and possibly of disease progression.