The development of perinatal brain connectivity underpins motor, cognitive and behavioural abilities in later life. Diffusion MRI allows the characterisation of subtle inter-individual differences in structural brain connectivity, though individual brain connectivity maps (connectomes) are by nature high in dimensionality and complex to interpret. Machine learning methods are a powerful tool to uncover properties of the connectome which are not readily visible and can give us clues as to how and why individual developmental trajectories differ. In this manuscript we used Deep Neural Networks and Random Forests to predict demographic and neurodevelopmental characteristics from neonatal structural connectomes in a large sample of babies (n = 524) from the developing Human Connectome Project. We achieved an accurate prediction of postmenstrual age (PMA) at scan in term-born infants (mean absolute error (MAE) = 0.72 weeks, r = 0.83 and p < 0.001). We also achieved good accuracy when predicting gestational age at birth in a cohort of term and preterm babies scanned at term equivalent age (MAE = 2.21 weeks, r = 0.82, p < 0.001). We subsequently used sensitivity analysis to obtain feature relevance from our prediction models, with the most important connections for prediction of PMA and GA found to predominantly involve frontal and temporal regions, thalami, and basal ganglia. From our models of PMA at scan for infants born at term, we computed a brain maturation index (predicted age minus actual age) of individual preterm neonates and found a significant correlation between this index and motor outcome at 18 months corrected age. Our results demonstrate the applicability of machine learning techniques in analyses of the neonatal connectome and suggest that a neural substrate of brain maturation with implications for future neurodevelopment is detectable at term equivalent age from the neonatal connectome.