Data on the impact of human papillomavirus (HPV) vaccination on the population HPV prevalence are largely obtained from women. We assessed the impact of the girls-only HPV16/18 vaccination program in the Netherlands that started in 2009, on trends in HPV prevalence among women and heterosexual men, using data from the PASSYON study. In this cross-sectional study, the HPV prevalence among 16- to 24-year-old visitors to sexually transmitted infection clinics was assessed in 2009, 2011, 2013, and 2015. We compared the genital postvaccination HPV prevalence with the prevaccination prevalence (2009) using Poisson GEE models. In total, we included 4,996 women and 1,901 heterosexual men. The percentage of women who reported to be vaccinated increased from 2.3% in 2009 to 37% in 2015. Among all women, the HPV16/18 prevalence decreased from 23% prevaccination to 15% in 2015 (adjusted prevalence ratio [aPR] 0.62, p