Background: We used graph theoretical analysis to quantify structural connectivity of the hippocampal-related episodic memory network and its association with memory performance in multiple sclerosis (MS) patients. Methods: Brain diffusion and T1-weighted sequences were obtained from 71 MS patients and 50 healthy controls (HCs). A total of 30 gray matter regions (selected a priori) were used as seeds to perform probabilistic tractography and create connectivity matrices. Global, nodal, and edge graph theoretical properties were calculated. In patients, verbal and visuospatial memory was assessed. Results: MS patients showed decreased network strength, assortativity, transitivity, global efficiency, and increased average path length. Several nodes had decreased strength and communicability in patients, whereas insula and left temporo-occipital cortex increased communicability. Patients had widespread decreased streamline count (SC) and communicability of edges, although a few ones increased their connectivity. Worse memory performance was associated with reduced network efficiency, decreased right hippocampus strength, and reduced SC and communicability of edges related to medial temporal lobe, thalamus, insula, and occipital cortex. Conclusion: Impaired structural connectivity occurs in the hippocampal-related memory network, decreasing the efficiency of information transmission. Network connectivity measures correlate with episodic memory, supporting the relevance of structural integrity in preserving memory processes in MS.