The World Health Organization has recommended the introduction of HPV vaccines into national immunization programme (NIP), but vaccination coverage remains low worldwide. We assessed the coverage and the parental acceptance of female and male HPV vaccination in Brazil after its introduction into the NIP. Methods We conducted a random-digit-dial survey of parents in seven major Brazilian cities from July-2015 to October-2016. A knowledge, attitude and practices questionnaire was developed and validated by expert analysis, semantic analysis, and pre-testing. Results 826 out of 2,324 (35.5%) eligible parents completed the interview. Parental acceptance of the HPV vaccine for daughters and sons 18 years of age or less was high (92% and 86%, respectively). Parents refusing vaccination were less likely to know that: HPV is sexually transmitted and causes genital warts, HPV vaccination is more beneficial before sexual debut, and HPV vaccine reactions are minor, and they were more likely to believe HPV vaccination can cause severe adverse events. Parents accepting HPV vaccine for daughters but not forsons were more likely to ignore that the vaccine is recommended for boys. Attitudes associated with HPV vaccine acceptance included: general belief in vaccines, trust in the NIP and in the HPV vaccine efficacy. Among girls eligible for HPV vaccination through the NIP, 58.4% had received a two-dose scheme and 71.1% at least one dose. “No vaccination/ missed vaccination at school” was the most common reason for missed HPV vaccination in the NIP.