Background: Cognitive decline remains difficult to predict as structural brain damage cannot fully explain the extensive heterogeneity found between MS patients. Objective: To investigate whether functional brain network organization measured with magnetoencephalography (MEG) predicts cognitive decline in MS patients after 5 years and to explore its value beyond structural pathology. Methods: Resting-state MEG recordings, structural MRI, and neuropsychological assessments were analyzed of 146 MS patients, and 100 patients had a 5-year follow-up neuropsychological assessment. Network properties of the minimum spanning tree (i.e. backbone of the functional brain network) indicating network integration and overload were related to baseline and longitudinal cognition, correcting for structural damage. Results: A more integrated beta band network (i.e. smaller diameter) and a less integrated delta band network (i.e. lower leaf fraction) predicted cognitive decline after 5 years ((Formula presented.)), independent of structural damage. Cross-sectional analyses showed that a less integrated network (e.g. lower tree hierarchy) related to worse cognition, independent of frequency band. Conclusions: The level of functional brain network integration was an independent predictive marker of cognitive decline, in addition to the severity of structural damage. This work thereby indicates the promise of MEG-derived network measures in predicting disease progression in MS.