Preterm infants are at high risk of neurodevelopmental impairment, which may be due to altered development of brain connectivity. We aimed to (i) assess structural brain development from 25 to 45 weeks gestational age (GA) using graph theoretical approaches and (ii) test the hypothesis that preterm birth results in altered white matter network topology. Sixty-five infants underwent MRI between 25(+3) and 45(+6) weeks GA. Structural networks were constructed using constrained spherical deconvolution tractography and were weighted by measures of white matter microstructure (fractional anisotropy, neurite density and orientation dispersion index). We observed regional differences in brain maturation, with connections to and from deep grey matter showing most rapid developmental changes during this period. Intra-frontal, frontal to cingulate, frontal to caudate and inter-hemispheric connections matured more slowly. We demonstrated a core of key connections that was not affected by GA at birth. However, local connectivity involving thalamus, cerebellum, superior frontal lobe, cingulate gyrus and short range cortico-cortical connections was related to the degree of prematurity and contributed to altered global topology of the structural brain network. The relative preservation of core connections at the expense of local connections may support more effective use of impaired white matter reserve following preterm birth.