Early identification of gestational diabetes mellitus (GDM) aims to reduce the risk of adverse maternal and perinatal outcomes. Currently, no circulating biomarker has proven clinically useful for accurate prediction of GDM. In this study, we tested if a panel of small non-coding circulating RNAs could improve early prediction of GDM. We performed a nested case-control study of participants from the European multicenter ‘Vitamin D and lifestyle intervention for GDM prevention (DALI)’ trial using serum samples from obese pregnant women (BMI ≥ 29 kg/m2) entailing 82 GDM cases (early- and late- GDM), and 41 age- and BMI-matched women with normal glucose tolerance (NGT) throughout pregnancy (controls). Anthropometric, clinical and biochemical characteristics were obtained at baseline (<20 weeks of gestation) and throughout gestation. Baseline serum microRNAs (miRNAs) were measured using quantitative real time PCR (qPCR). Elevated miR-16-5p, -29a-3p, and -134-5p levels were observed in women, who were NGT at baseline and later developed GDM, compared with controls who remained NGT. A combination of the three miRNAs could distinguish later GDM from NGT cases (AUC 0.717, p = 0.001, compared with fasting plasma glucose (AUC 0.687, p = 0.004)) as evaluated by area under the curves (AUCs) using Receiver Operator Characteristics (ROC) analysis. Elevated levels of individual miRNAs or a combination hereof were associated with higher odds ratios of GDM. Conclusively, circulating miRNAs early in pregnancy could serve as valuable predictive biomarkers of GDM.