Abstract There is emerging evidence for delayed brain development in neonates with congenital heart disease. We hypothesize that the perioperative development of the structural brain connectome is a proxy to such delays. Therefore, we set out to quantify the alterations and longitudinal pre- to post-operative changes in the connectome in congenital heart disease neonates relative to healthy term newborns and assess factors contributing to disturbed perioperative network development. In this prospective cohort study, 114 term neonates with congenital heart disease underwent cardiac surgery at the University Children’s Hospital Zurich. Forty-six healthy term newborns were included as controls. Pre- and post-operative structural connectomes were derived from mean fractional anisotropy values of fibre pathways traced using diffusion MR tractography. Graph theory parameters calculated across a proportional cost threshold range were compared between groups by multi-threshold permutation correction adjusting for confounders. Network-based statistic was calculated for edgewise network comparison. White-matter injury volume was quantified on 3D T1-weighted images. Random coefficient mixed models with interaction terms of (i) cardiac subtype and (ii) injury volume with post-menstrual age at MRI, respectively, were built to assess modifying effects on network development. Pre- and post-operatively, at the global level, efficiency, indicative of network integration, was lower in heart disease neonates than controls. In contrast, local efficiency and transitivity, indicative of network segregation, were higher compared to controls (all P < 0.025 for one-sided t-tests). Pre-operatively, these group differences were also found across multiple widespread nodes (all P < 0.025, accounting for multiple comparison), whereas post-operatively nodal differences were not evident. At the edge-level, the majority of weaker connections in heart disease neonates compared to controls involved inter-hemispheric connections (66.7% pre-operatively; 54.5% post-operatively). A trend showing a more rapid pre- to post-operative decrease in local efficiency was found in class I cardiac sub-type (biventricular defect without aortic arch obstruction) compared to controls. In congenital heart disease neonates, larger white-matter injury volume was associated with lower strength (P = 0.0026) and global efficiency (P = 0.0097). The maturation of the structural connectome is delayed in congenital heart disease neonates, with a pattern of lower structural integration and higher segregation compared to controls. Trend-level evidence indicated that normalized post-operative cardiac physiology in class I sub-types might improve structural network topology. In contrast, the burden of white-matter injury negatively impacts network strength and integration. Further research is needed to elucidate how aberrant structural network development in congenital heart disease represents neural correlates of later neurodevelopmental impairments.