Abstract Background The Dutch Human Papillomavirus (HPV) catch-up vaccination program in 2009 appeared less successful than expected. We aimed to identify the most important determinants of refusing the vaccination. Methods Two thousand parents of girls born in 1996 targeted for HPV vaccination received an invitation letter to participate in a questionnaire study. Two study groups were defined: the first group consisted of parents of girls who had accepted the vaccine and already received the first dose of HPV vaccination. The second group consisted of parents whose daughters were not vaccinated. The questionnaire consisted of a broad spectrum of possible determinants that were revealed after literature search and discussions with the stakeholders. Results Four hundred sixty nine questionnaires (24%) were returned, 307 (31%) from those who accepted and 162 (16%) from those who declined the vaccine. The decision not to accept the vaccine was largely determined by: (i) perception that the information provided by the government about the vaccine was limited or biased (OR 13.27); (ii) limited trust, that the government would stop the vaccination program if there were serious side effects (OR 9.95); (iii) lack of knowledge about the effectiveness of the vaccine (OR 7.67); (iv) concerns about the side effects of the vaccine (OR 4.94); (v) lack of conviction that HPV can be extremely harmful (OR 3.78); (vi) perception that the government is strongly influenced by vaccine producers (OR 3.54); and (vii) religious convictions (OR 2.18). Conclusions This study revealed several determinants for HPV vaccination uptake after implementation of the HPV vaccine for adolescent girls. These determinants should be taken into consideration in order to successfully implement HPV vaccination into National Immunization Programs.