Biomarkers to identify women at risk of cervical cancer among those with high-risk HPV infection (hrHPV+) are needed. Deregulated expression of microRNAs (miRNAs) contributes to hrHPV-induced cervical carcinogenesis. We aimed at identifying miRNAs with the capacity to distinguish high (CIN2+) and low (≤ CIN1) grade cervical lesions. We sequenced miRNA libraries from Formalin-Fixed Paraffin-Embedded (FFPE) tissues from women with CIN2+ (n = 10) and age-matched women with ≤ CIN1 (n = 10), randomly and retrospectively selected from a trial that followed women for 24 months after a hrHPV+ test at the screening visit. Five miRNAs differentially expressed were validated by RT-qPCR in an independent set of FFPE tissues with a reviewed diagnosis of CIN2+ (n = 105) and ≤ CIN1 (n = 105). The Ingenuity Pathway Analysis (IPA) was conducted to identify mRNAs inversely correlated with the top 25 differentially expressed miRNAs. Inverse correlations with 401 unique mRNA targets were identified for fourteen of the top 25 differentially expressed miRNAs. Eleven of these miRNAs targeted 26 proteins of pathways deregulated by HPV E6 and E7 oncoproteins and two of them, miR-143-5p and miR-29a-3p, predicted CIN2+ and CIN3+ in the independent validation by RT-qPCR of FFPE tissues from hrHPV-positive women.