Background: With the implementation of primary high-risk human papillomavirus (hrHPV) screening in the Netherlands, an increase was observed in the number of unnecessary referrals (≤Cervical Intraepithelial Neoplasia (CIN) 1) to colposcopy. We aimed to investigate which alternative triage strategies safely reduce unnecessary referrals in HPV-based cervical cancer screening programmes. Methods: Microsimulation model MISCAN was used to simulate an unvaccinated cohort of ten million 30-year old Dutch women. We calculated unnecessary referrals, cervical cancer incidence, mortality, costs and QALYs for 24 triage strategies. Condition for direct referral (atypical squamous cells of undetermined significance (ASC-US), low-grade squamous intraepithelial lesions (LSIL), high-grade squamous intraepithelial lesions (HSIL), conditional on HPV-genotype 16/18/other high risk (OHR)), type of triage test (cytology alone or combined with hrHPV) and time to triage test (6 or 12 months) was varied. Results: The 24 triage strategies had varying effects on the number of unnecessary referrals ranging from −72% to +35%. Adjusting conditions for referral to ‘HPV16/18+ and ASC-US+’ and ‘HPVOHR+ and HSIL+’ and extending the interval between tests to 12 months resulted in a reduction in unnecessary referrals of 40% (incidence +0%, mortality −1%). Reduction in unnecessary referrals without genotyping was achieved by adjusting conditions for direct referral to LSIL (12 months to repeat test) (unnecessary referrals −37%, incidence +2%, mortality +0%). Conclusions: To reduce the number of unnecessary referrals without increasing incidence and mortality by more than 2% in the Dutch cervical cancer screening programme, genotyping for HPV16 or HPV16/18 should be implemented with 12 months to repeat testing.