In recent years, vaccination coverage rates against Human Papilloma Virus (HPV) in Europe have shown a decreasing trend and remain below the required standard. The present study aims to assess knowledge and attitudes regarding HPV infection and vaccination among a representative sample of preadolescents of Palermo, Italy. A survey was carried out throughout two questionnaires, before and after carrying out an educational intervention scheduled during school hours. A total of 1702 students attending first-grade secondary schools of the province of Palermo were enrolled (response rate 68.9%). Students attending third classes (adj OR = 1.18; CI 95% 1.03–1.36), being of higher socioeconomic status (adj OR = 1.35; CI 95% 1.05–1.73), who had previously received information about sexually transmitted diseases (STDs) at home (adj OR = 1.62; CI 95% 1.27–2.07) or at school (adj OR = 2.15; CI 95% 1.70–2.71) and who had ever heard in the past about HPV (adj OR = 1.80; CI 95% 1.42–2.29) showed a significantly higher baseline level of knowledge regarding HPV. Willingness to receive HPV vaccination, in a 10-point Likert scale, significantly increased between the pre-(8.51; SD ± 1.79) and post-(9.01 SD ± 1.52) intervention questionnaires (p < 0.001). A total of 188 out of 272 (69.1%) preadolescents attending five out eighteen schools involved in the project, who had not previously received the HPV vaccine, were vaccinated. During past years, education campaigns on HPV were mainly dedicated to adult women, excluding teenagers and omitting young males. It should therefore be of primary importance that school-based education and vaccination programmes be standardized.