It is well acknowledged that HPV testing should not be performed at young age and at short intervals. Cytological screening practices have shown that over-screening, i.e., from a younger age and at shorter intervals than recommended, is hard to avoid. We quantified the consequences of a switch to primary HPV screening for over-screened women, taking into account its higher sensitivity but lower specificity than cytology. The health effects of using the HPV test instead of cytology as the primary screening method were determined with the MISCAN-Cervix model. We varied the age women start screening and the interval between screens. In the sensitivity analyses, we varied the background risk of cervical cancer, the HPV prevalence, the discount rate, the triage strategy after cytology, and the test characteristics of both cytology and the HPV test. For women screened 5 yearly from age 30, 32 extra deaths per 100,000 simulated women were prevented when switching from primary cytology to primary HPV testing. For annual screening from age 20, such a switch resulted in 6 extra deaths prevented. It was associated with 9,044 more positive primary screens in the former scenario versus 76,480 in the latter. Under all conditions, for women screened annually, switching to HPV screening resulted in a net loss of quality-adjusted life years. For over-screened women, the harms associated with a lower test specificity outweigh the life years gained when switching from primary cytology to primary HPV testing. The extent of over-screening should be considered when deciding on inclusion of primary HPV screening in cervical cancer screening guidelines.