Objective: To investigate the dynamic temporal changes of brain resting-state functional connectivity (RS-FC) following mental effort in multiple sclerosis (MS) patients with cognitive fatigue (CF). Methods: Twenty-two MS patients, 11 with (F) and 11 without CF, and 12 healthy controls were included. Separate RS-FC scans were acquired on a 3T MR scanner immediately before ( t0), immediately after ( t1) and 30 minutes after ( t2) execution of the paced auditory serial addition test (PASAT), a cognitively demanding task. Subjectively perceived CF after PASAT execution was also assessed. RS-FC changes were investigated by using a data-driven approach (the Intrinsic Connectivity Contrast_-power), complemented by a priori defined regions of interest analyses. Results: The F-group patients experienced stronger RS-FC at t2 between the left superior frontal gyrus (L-SFG) and occipital, frontal and temporal areas, which increased over time after PASAT execution. In the F-group patients, the L-SFG was hyperconnected at t1 with the left caudate nucleus and hypoconnected at t2 with the left anterior thalamus. These variations were correlated with both subjectively perceived and clinically assessed CF, and—for the left thalamus—with PASAT performance. Conclusion: The development of cortico–cortical and cortico–subcortical hyperconnectivity following mental effort is related to CF symptoms in MS patients.