Fatigue is frequent and disabling in persons with multiple sclerosis (pwMS) with mild neurological disability. These patients also have impaired physical fitness. Whether mildly disabled pwMS are deconditioned, and this deconditioning is linked to fatigue, remains unknown. Our aim is to determine the physical fitness of mildly disabled patients with multiple sclerosis and study its relationship with perceived fatigue and to link perceived fatigue with other parameters. Twenty patients (14 women; mean age: 45.5 years) with mild disability (Expanded Disability Status Scale 0–4) underwent a 2-min walking test, Timed Up-and-Go test, aerobic capacity testing, and isometric knee extension testing to assess strength and neuromuscular fatigability. They completed questionnaires assessing perceived fatigue, psychological status, and physical activity. Correlation coefficients and multivariate regression were used to analyze the relationships among variables. Seventeen (85%) patients reported a high level of fatigue. Thirteen (65%) patients had subnormal aerobic capacity. Fatigue was weakly to moderately associated with aerobic capacity, mobility, walking capacity, depression, and neuromuscular fatigability. An association of disease duration, aerobic capacity, and the neuromuscular fatigability index explained 65.1% of fatigue. A high proportion of pwMS with mild neurological disability are fatigued and deconditioned. Perceived fatigue is linked to aerobic capacity, neuromuscular fatigability, depression, mobility, and walking capacity. Focusing on these parameters could help in the management of fatigue.