Attention and executive deficits are disabling symptoms in multiple sclerosis (MS) that have been related to disconnection mechanisms. We aimed to investigate changes in structural connectivity in MS and their association with attention and executive performance applying an improved framework that combines high order probabilistic tractography and anatomical exclusion criteria postprocessing. We compared graph theory metrics of structural networks and fractional anisotropy (FA) of white matter (WM) connections or edges between 72 MS subjects and 38 healthy volunteers (HV) and assessed their correlation with cognition. Patients displayed decreased network transitivity, global efficiency and increased path length compared with HV (p < 0.05, corrected). Also, nodal strength was decreased in 26 of 84 gray matter regions. The distribution of nodes with stronger connections or hubs of the network was similar among groups except for the right pallidum and left insula, which became hubs in patients. MS subjects presented reduced edge FA widespread in the network, while FA was increased in 24 connections (p < 0.05, corrected). Decreased integrity of frontoparietal networks, deep gray nuclei and insula correlated with worse attention and executive performance (r between 0.38 and 0.55, p < 0.05, corrected). Contrarily, higher strength in the right transverse temporal cortex and increased FA of several connections (mainly from cingulate, frontal and occipital cortices) were associated with worse functioning (r between −0.40 and −0.47, p < 0.05 corrected). In conclusion, structural brain connectivity is disturbed in MS due to widespread impairment of WM connections and gray matter structures. The increased edge connectivity suggests the presence of reorganization mechanisms at the structural level. Importantly, attention and executive performance relates to frontoparietal networks, deep gray nuclei and insula. These results support the relevance of network integrity to maintain optimal cognitive skills.