Background: Coordinated patterns of gray matter morphology can be represented as networks, and network disruptions may explain cognitive dysfunction related to multiple sclerosis (MS). Objective: To investigate whether single-subject gray matter network properties are related to impaired cognition in MS. Methods: We studied 148 MS patients (99 female) and 33 healthy controls (HC, 21 female). Seven network parameters were computed and compared within MS between cognitively normal and impaired subjects, and associated with performance on neuropsychological tests in six cognitive domains with regression models. Analyses were controlled for age, gender, whole-brain gray matter volumes, and education level. Results: Compared to MS subjects with normal cognition, MS subjects with cognitive impairment showed a more random network organization as indicated by lower lambda values (all p < 0.05). Worse average cognition and executive function were associated with lower lambda values. Impaired information processing speed, working memory, and attention were associated with lower clustering values. Conclusion: Our findings indicate that MS subjects with a more randomly organized gray matter network show worse cognitive functioning, suggesting that single-subject gray matter graphs may capture neurological dysfunction due to MS.