Although previous investigations of transsexual people have focused on regional brain alterations, evaluations on a network level, especially those structural in nature, are largely missing. Therefore, we investigated the structural connectome of 23 female-to-male (FtM) and 21 male-to-female (MtF) transgender patients before hormone therapy as compared with 25 female and 25 male healthy controls. Graph theoretical analysis of whole-brain probabilistic tractography networks (adjusted for differences in intracranial volume) showed decreased hemispheric connectivity ratios of subcortical/limbic areas for both transgender groups. Subsequent analysis revealed that this finding was driven by increased interhemispheric lobar connectivity weights (LCWs) in MtF transsexuals and decreased intrahemispheric LCWs in FtM patients. This was further reflected on a regional level, where the MtF group showed mostly increased local efficiencies and FtM patients decreased values. Importantly, these parameters separated each patient group from the remaining subjects for the majority of significant findings. This work complements previously established regional alterations with important findings of structural connectivity. Specifically, our data suggest that network parameters may reflect unique characteristics of transgender patients, whereas local physiological aspects have been shown to represent the transition from the biological sex to the actual gender identity.