In 2019, the WHO has announced that it will intensify efforts to eliminate cervical cancer worldwide by increasing coverage of the HPV (Human Papillomavirus) vaccine. Finding reasons for low HPV vaccine coverage and looking for solutions to address the problem should be the priorities for public health. The municipality of Wroclaw (Poland) attempted to meet the challenge earlier by introducing a Prophylaxis Program against HPV in 2010. The core of the program are educational meetings at schools and free vaccinations offered at GP offices. After five successful years (vaccination coverage >80% fully vaccinated), vaccination uptake declined to 61.8%. A survey was carried out in 2015 to verify the experience concerning the Program among 1360 volunteers. Three groups were surveyed: parents (n = 509), teenage girls (n = 748) and nurses who performed the vaccinations (n = 103). What is noteworthy in the results there are factors that positively influenced vaccine acceptance: education offered within the program; the fact that the vaccinations are offered free of charge and the experience of earlier vaccination. It turned out that fear of side effects and the lack of trust in vaccination effectiveness were the most common reasons for vaccination refusal. Most nurses underestimated their role in building vaccination acceptance and 7.1% of them felt uncertain administrating the vaccination. Conslusions: the vaccination delivery strategy should be reconsidered; interventions to raise the nurses' awareness of their role in building vaccine acceptance should be improved; the 13th year of life is the best moment to offer a vaccination.