Purpose: To investigate the structural brain connectome in patients with Parkinson disease (PD) and mild cognitive impairment (MCI) and in patients with PD without MCI. Materials and Methods: This prospective study was approved by the local ethics committees, and written informed consent was obtained from all subjects prior to enrollment. The individual structural brain connectome of 170 patients with PD (54 with MCI, 116 without MCI) and 41 healthy control subjects was obtained by using deterministic diffusion-tensor tractography. A network-based statistic was used to assess structural connectivity differences among groups. Results: Patients with PD and MCI had global network alterations when compared with both control subjects and patients with PD without MCI (range, P = .004 to P = .048). Relative to control subjects, patients with PD and MCI had a large basal ganglia and frontoparietal network with decreased fractional anisotropy (FA) in the right hemisphere and a subnetwork with increased mean diffusivity (MD) involving similar regions bilaterally (P <.01). When compared with patients with PD without MCI, those with PD and MCI had a network with decreased FA, including basal ganglia and frontotemporoparietal regions bilaterally (P, .05). Similar findings were obtained by adjusting for motor disability (P <.05, permutation-corrected P = .06). At P <.01, patients with PD and MCI did not show network alterations relative to patients with PD without MCI. Network FA and MD values were used to differentiate patients with PD and MCI from healthy control subjects and patients with PD without MCI with fair to good accuracy (cross-validated area under the receiver operating characteristic curve [principal + secondary connected components] range, 0.75-0.85). Conclusion: A disruption of structural connections between brain areas forming a network contributes to determine an altered information integration and organization and thus cognitive deficits in patients with PD. These results provide novel information concerning the structural substrates of MCI in patients with PD and may offer markers that can be used to differentiate between patients with PD and MCI and patients with PD without MCI.