Fatigue in people with Multiple Sclerosis (PwMS) is a poorly understood, complex, and disabling symptom. We hypothesized that the perception of fatigue in PwMS results from increased information processing in cortical areas responsible for the perception of bodily states and decreased information processing in the cortico-basal ganglia network involved in the perception of motor performance. We investigated whether PwMS who perceive excessive fatigue would have increased resting-state functional connectivity (rsFC) between interoceptive brain areas (amygdala, anterior cingulate cortex [ACC], and insula) and decreased rsFC between cortico-basal ganglia premotor network compared to PwMS not reporting fatigue. Twenty-three relapsing-remitting PwMS were divided into fatigued versus non-fatigued groups based on the Modified Fatigue Impact Scale score (≥38 points). Age-matched healthy controls (n = 21) were also analyzed. All the participants underwent resting-state functional magnetic resonance imaging. PwMS who perceived abnormal fatigue, compared to non-fatigued PwMS, showed reduced rsFC between cortico-basal ganglia network and increased rsFC within interoceptive brain areas (amygdala, ACC, and insula) involved in perception of bodily states (P ≤ 0.01). Increased rsFC within interoceptive brain areas was specific for fatigued PwMS as this result did not appear when comparing PwMS (fatigued and non-fatigued) with healthy controls. The Modified Fatigue Impact Scale scores were correlated with the increased rsFC between interoceptive brain areas (amygdala and insula) and decreased rsFC between cortico-basal ganglia (P < 0.01). MS-related perceived fatigue has a central cause, and it may be due to increased interoceptive brain activity (perception of bodily states). Interventions are needed to decrease fatigue and reorganize the brain circuitry.