Background: The first HPV-vaccine eligible cohorts in the Netherlands will enter the cervical screening program in 2023. However, a substantial number of young women already have had a cervical sample taken before entry into the regular screening program. This study was initiated to explore early effects of HPV vaccination on detection of cytological abnormalities in cervical samples of women younger than the screening age. Methods: Results of cervical samples were obtained from the Dutch National Pathology Databank (PALGA) and were linked to the women's HPV vaccination status from the national vaccination registry (Praeventis) (N = 42,171). Occurrence of low-grade and high-grade squamous intraepithelial lesions or worse (LSIL and HSIL+) and high-risk HPV positive tests (hrHPV) in the first cervical sample were compared between vaccinated and unvaccinated women by multivariable logistic regression analysis, corrected for age at cervical sampling and age of vaccination (12/13 years, ≥ = 14 years). Results: For fully vaccinated women (three- or two-dose schedule), statistically significant reductions were seen for all outcomes compared to unvaccinated women (hrHPV: adjusted OR, 0.70, 95% CI, 0.63–0.79; LSIL: 0.70, 0.61–0.80; HSIL+: 0.39, 0.30–0.51). Conclusions: By linking nation-wide registries on pathology and vaccination, we show significant beneficial early effects of HPV-vaccination on LSIL, HSIL+, CIN3/AIS/carcinoma and hrHPV detection in young women upto 24 years of age who have a cervical sample taken before entry into the cervical cancer screening program.