Background: Fatigue is one of the most frequent and disabling symptoms in multiple sclerosis, but its pathophysiological mechanisms are poorly understood. It is in particular unclear whether and how fatigue relates to structural and functional brain changes. Objective: We aimed to analyse the association of fatigue severity with basal ganglia functional connectivity, basal ganglia volumes, white matter integrity and grey matter density. Methods: In 44 patients with relapsing–remitting multiple sclerosis and 20 age- and gender-matched healthy controls, resting-state fMRI, diffusion tensor imaging and voxel-based morphometry was performed. Results: In comparison with healthy controls, patients showed alteration of grey matter density, white matter integrity, basal ganglia volumes and basal ganglia functional connectivity. No association of fatigue severity with grey matter density, white matter integrity and basal ganglia volumes was observed within patients. In contrast, fatigue severity was negatively correlated with functional connectivity of basal ganglia nuclei with medial prefrontal cortex, precuneus and posterior cingulate cortex in patients. Furthermore, fatigue severity was positively correlated with functional connectivity between caudate nucleus and motor cortex. Conclusion: Fatigue is associated with distinct alterations of basal ganglia functional connectivity independent of overall disability. The pattern of connectivity changes suggests that disruption of motor and non-motor basal ganglia functions, including motivation and reward processing, contributes to fatigue pathophysiology in multiple sclerosis.