Spontaneous Preterm Delivery (sPTD) is one of the leading causes of perinatal mortality and morbidity worldwide. The present case–control study aims to detect miRNAs differentially expressed in the first trimester maternal plasma with the view to identify predictive biomarkers for sPTD, between 320/7 and 366/7 weeks, that will allow for timely interventions for this serious pregnancy complication. Small RNA sequencing (small RNA-seq) of five samples from women with a subsequent sPTD and their matched controls revealed significant down-regulation of miR-23b-5p and miR-125a-3p in sPTD cases compared to controls, whereas miR-4732-5p was significantly overexpressed. Results were confirmed by qRT-PCR in an independent cohort of 29 sPTD cases and 29 controls. Statistical analysis demonstrated that miR-125a is a promising early predictor for sPTL (AUC: 0.895; 95% CI: 0.814-0.972; p < 0.001), independent of the confounding factors tested, providing a useful basis for the development of a novel non-invasive predictive test to assist clinicians in estimating patient-specific risk.