Neonates with complex congenital heart disease (CHD) demonstrate microstructural brain dysmaturation, but the relationship with structural network topology is unknown. We performed diffusion tensor imaging (DTI) in term neonates with CHD preoperatively (N = 61) and postoperatively (N = 50) compared with healthy term controls (N = 91). We used network topology (graph) analyses incorporating different weighted and unweighted approaches and subject‐specific white matter segmentation to investigate structural topology differences, as well as a voxel‐based analysis (VBA) to confirm the presence of microstructural dysmaturation. We demonstrate cost‐dependent network inefficiencies in neonatal CHD in the pre‐ and postoperative period compared with controls, related to microstructural differences. Controlling for cost, we show the presence of increased small‐worldness (hierarchical fiber organization) in CHD infants preoperatively, that persists in the postoperative period compared with controls, suggesting the early presence of brain reorganization. Taken together, topological microstructural dysmaturation in CHD infants is accompanied by hierarchical fiber organization during a protracted critical period of early brain development. Our methodology also provides a pipeline for quantitation of network topology changes in neonates and infants with microstructural brain dysmaturation at risk for perinatal brain injury.