Background Vaccination against the oncogenic human papillomavirus (HPV) types 16 and 18 will reduce the prevalence of these types, thereby also reducing cervical cancer risk in unvaccinated women. This (measurable) herd effect will be limited at first, but is expected to increase over time. At a certain herd immunity level, tailoring screening to vaccination status may no longer be worth the additional effort. Moreover, uniform screening may be the only viable option. We therefore investigated at what level of herd immunity it is cost-effective to also reduce screening intensity in unvaccinated women. Methods We used the MISCAN-Cervix model to determine the optimal screening strategy for a pre-vaccination population and for vaccinated women (similar to 80% decreased risk), assuming a willingness- to-pay of (sic)50,000 per quality-adjusted life year gained. We considered HPV testing, cytology testing and co-testing and varied the start age of screening, the screening interval and the number of lifetime screens. We then calculated the incremental cost-effectiveness ratio (ICER) of screening unvaccinated women with the strategy optimized to the pre-vaccination population as compared to with the strategy optimized to vaccinated women, assuming different herd immunity levels. Results Primary HPV screening with cytology triage was the optimal strategy, with 8 lifetime screens for the pre-vaccination population and 3 for vaccinated women. The ICER of screening unvaccinated women 8 times instead of 3 was (sic)28,085 in the absence of herd immunity. At around 50% herd immunity, the ICER reached (sic)50,000. Conclusion From a herd immunity level of 50% onwards, screening intensity based on the pre-vaccination risk level becomes cost-ineffective for unvaccinated women. Reducing the screening intensity of uniform screening may then be considered.