Background: The introduction of primary HPV screening has doubled the number of colposcopy referrals because of the direct referral of HPV-positive women with a borderline or mild dyskaryosis (BMD) cytology (ASC-US/LSIL) triage test. Further risk-stratification is warranted to improve the efficiency of HPV-based screening. Methods: This study evaluated the discriminative power of FAM19A4/miR124-2 methylation, HPV16/18 genotyping and HPV16/18/31/33/45 genotyping in HPV-positive women with BMD (n = 294) in two Dutch screening trials. Absolute CIN3+ risks and colposcopy referrals within one screening round were calculated. Results: Methylation analysis discriminated well, yielding a CIN3+ risk of 33.1% after a positive result and a CIN3+ risk of 9.8% after a negative result. HPV16/18 and HPV16/18/31/33/45 genotyping resulted in a 27.6% and 24.6% CIN3+ risk after a positive result, and a 13.2% and 9.1% CIN3+ risk after a negative result. Colposcopy referral percentages were 41.2%, 43.2%, and 66.3% for FAM19A4/miR124-2 methylation, HPV16/18 and HPV16/18/31/33/45 genotyping, respectively. The CIN3+ risk after a negative result could be lowered to 2.8% by combining methylation and extended genotyping, at the expense of a higher referral percentage of 75.5%. Conclusion: The use of FAM19A4/miR124-2 methylation and/or HPV genotyping in HPV-positive women with BMD can lead to a substantial reduction in the number of direct colposcopy referrals.