Children with Congenital Heart Disease (CHD) are at increased risk of neurodevelopmental impairments. The neonatal antecedents of impaired behavioural development are unknown. 43 infants with CHD underwent presurgical brain diffusion-weighted MRI [postmenstrual age at scan median (IQR) = 39.29 (38.71–39.71) weeks] and a follow-up assessment at median age of 22.1 (IQR 22.0–22.7) months in which parents reported internalizing and externalizing problem scores on the Child Behaviour Checklist. We constructed structural brain networks from diffusion-weighted MRI and calculated edge-wise structural connectivity as well as global and local brain network features. We also calculated presurgical cerebral oxygen delivery, and extracted perioperative variables, socioeconomic status at birth and a measure of cognitively stimulating parenting. Lower degree in the right inferior frontal gyrus (partial ρ = −0.687, p < 0.001) and reduced connectivity in a frontal-limbic sub-network including the right inferior frontal gyrus were associated with higher externalizing problem scores. Externalizing problem scores were unrelated to neonatal clinical course or home environment. However, higher internalizing problem scores were associated with earlier surgery in the neonatal period (partial ρ = −0.538, p = 0.014). Our results highlight the importance of frontal-limbic networks to the development of externalizing behaviours and provide new insights into early antecedents of behavioural impairments in CHD.