Human papillomavirus infection is a cause of the development of invasive cervical cancer. Three types of vaccine are currently available to prevent precancerous/cancerous lesions due to persistent infection, which is supported mainly by 7 different high-risk genotypes. The aim of this pilot study was to acquire preliminary data on type-specific prevalence 10 years after the implementation of the HPV vaccination program in Italy, in order to subsequently plan appropriate observational studies in the Italian population. First-voided urine samples were collected from 393 consenting subjects, both females and males, aged 18–40 years, and HPV DNA was detected by PCR amplification of a 450 bp L1 fragment. All amplified products were genotyped by means of the Restriction Fragment Length Polymorphism (RFLP) method. The female population was divided into three cohorts (“vaccine-eligible”, “pre-screening” and “screening” cohorts) according to the preventive intervention scheduled by age; males were included in the same three cohorts according to their year of birth. The overall prevalence of HPV infection was 19%, being higher in females than in males (22.1% vs. 13.6%, p = 0.03729). In the female population, 10 years after the start of the national immunization program, we observed a reduction in the prevalence of vaccine types and the number of circulating genotypes, especially in the “vaccine-eligible” cohort. The frequency of HPV vaccine types increased with age, particularly in males in the “pre-screening” and “screening” cohorts. Our study highlights the importance of monitoring HPV infection in both genders, to validate the effect of the HPV vaccination program.