Background: More than 80% of multiple sclerosis (MS) patients experience symptoms of fatigue. MS-related fatigue is only partly explained by structural (lesions and atrophy) and functional (brain activation and conventional static functional connectivity) brain properties. Objectives: To investigate the relationship of dynamic functional connectivity (dFC) with fatigue in MS patients and to compare dFC with commonly used clinical and MRI parameters. Methods: In 35 relapsing-remitting MS patients (age: 42.83 years, female/male: 20/15, disease duration: 11 years) and 19 healthy controls (HCs) (age: 41.38 years, female/male: 11/8), fatigue was measured using the CIS-20r questionnaire at baseline and at 6-month follow-up. All subjects underwent structural and resting-state functional MRI at baseline. Global static functional connectivity (sFC) and dynamic functional connectivity (dFC) were calculated. dFC was assessed using a sliding-window approach by calculating the summed difference (diff) and coefficient of variation (cv) across windows. Moreover, regional connectivity between regions previously associated with fatigue in MS was estimated (i.e. basal ganglia and regions of the Default Mode Network (DMN): medial prefrontal, posterior cingulate and precuneal cortices). Hierarchical regression analyses were performed with forward selection to identify the most important correlates of fatigue at baseline. Results were not corrected for multiple testing due to the exploratory nature of the study. Results: Patients were more fatigued than HCs at baseline (p = 0.001) and follow-up (p = 0.002) and fatigue in patients was stable over time (p = 0.213). Patients had significantly higher baseline global dFC than HCs, but no difference in basal ganglia-DMN dFC. In the regression model for baseline fatigue in patients, basal ganglia-DMN dFC-cv (standardized β = -0.353) explained 12.5% additional variance on top of EDSS (p = 0.032). Post-hoc analysis revealed higher basal ganglia-DMN dFC-cv in non-fatigued patients compared to healthy controls (p = 0.013), whereas fatigued patients and healthy controls showed similar basal ganglia-DMN dFC. Conclusions: Less dynamic connectivity between the basal ganglia and the cortex is associated with greater fatigue in MS patients, independent of disability status. Within patients, lower dynamics of these connections could relate to lower efficiency and increased fatigue. Increased dynamics in non-fatigued patients compared to healthy controls might represent a network organization that protects against fatigue or signal early network dysfunction.