The brain connectome of multiple sclerosis (MS) has been investigated by several previous studies; however, it is still unknown how the network changes in clinically isolated syndrome (CIS), the earliest stage of MS, and how network alterations on a functional level relate to the structural level in MS disease. Here, we investigated the topological alterations of both the structural and functional connectomes in 41 CIS and 32 MS patients, compared to 35 healthy controls, by combining diffusion tensor imaging and resting-state functional MRI with graph analysis approaches. We found that the structural connectome showed a deviation from the optimal pattern as early as the CIS stage, while the functional connectome only showed local changes in MS patients, not in CIS. When comparing two patient groups, the changes appear more severe in MS. Importantly, the disruptions of structural and functional connectomes in patients occurred in the same direction and locally correlated in sensorimotor component. Finally, the extent of structural network changes was correlated with several clinical variables in MS patients. Together, the results suggested early disruption of the structural brain connectome in CIS patients and provided a new perspective for investigating the relationship of the structural and functional alterations in MS.