BACKGROUND: There are few data on factors influencing human papillomavirus (HPV) vaccination uptake in sub-Saharan Africa. We examined the characteristics of receivers and non-receivers of HPV vaccination in Tanzania and identified reasons for not receiving the vaccine. METHODS: We conducted a case control study of HPV vaccine receivers and non-receivers within a phase IV cluster-randomised trial of HPV vaccination in 134 primary schools in Tanzania. Girls who failed to receive vaccine (pupil cases) and their parents/guardians (adult cases) and girls who received dose 1 (pupil controls) of the quadrivalent vaccine (Gardasil™) and their parents/guardians (adult controls) were enrolled from 39 schools in a 1∶1 ratio and interviewed about cervical cancer, HPV vaccine knowledge and reasons why they might have received or not received the vaccine. Conditional logistic regression was used to determine factors independently associated with not receiving HPV vaccine. RESULTS: We interviewed 159 pupil/adult cases and 245 pupil/adult controls. Adult-factors independently associated with a daughter being a case were older age, owning fewer household items, not attending a school meeting about HPV vaccine, and not knowing anyone with cancer. Pupil-factors for being a case included having a non-positive opinion about the school de-worming programme, poor knowledge about the location of the cervix, and not knowing that a vaccine could prevent cervical cancer. Reasons for actively refusing vaccination included concerns about side effects and infertility. Most adult and pupil cases reported that they would accept the HPV vaccine if it were offered again (97% and 93% respectively). CONCLUSIONS: Sensitisation messages, especially targeted at older and poorer parents, knowledge retention and parent meetings are critical for vaccine acceptance in Tanzania. Vaccine side effects and fertility concerns should be addressed prior to a national vaccination program. Parents and pupils who initially decline vaccination should be given an opportunity to reconsider their decision.