The cerebellum is involved in multiple sclerosis (MS), but its implication in early phases is still poorly understood. We investigated structural and functional cerebellar connectivity alterations in early and minimally impaired MS patients, and their correlation to patients’ clinical status. We reconstructed the connectomes of 28 MS patients and 16 healthy controls and performed network statistical analysis. Structural connectivity was found to be altered independently from cerebellar lesion count, volume and disease duration; the microstructural properties of altered connections correlated with patients’ motor and cognitive performance. No topological reorganization or compensatory mechanisms were observed at this stage.