© 2016, Springer Science+Business Media New York. Objectives We examined variation in primary care physicians’ (PCPs’) perceptions of barriers to physician-initiated discussion of HPV vaccination, and how this is associated with the rates at which they discuss, initiate and continue to administer vaccination with 11–12 year-old girls. Methods We surveyed 301 PCPs using systematic random sampling. PCP variation in perceived barriers to discussing HPV vaccination was modeled using latent class analysis (LCA). The distinct PCP groups identified were compared with each other using three iterative logistic regression models to predict the likelihood of initiating vaccine discussion and the reported percentages of 11–12 year-old patients who initiated HPV vaccination and received follow-up shots. Results LCA revealed three groups of PCPs who perceived major, moderately significant and relatively minor barriers (17.9, 41.9 and 40.2 % of respondents, respectively). Pediatricians, PCPs who were female, had minority racial/ethnic status and who perceived only minor barriers had significantly higher odds of initiating discussion. PCPs were more likely to initiate HPV vaccination if they had initiated discussion and perceived minor or moderate communication barriers. Increased likelihood to administer follow-up HPV vaccine was associated with having initiated discussion, perceiving only minor barriers and working outside Deep South states, but not with having initiated vaccination. Conclusions for Practice PCPs who discuss HPV vaccination with girls aged 11–12 and their mothers are more likely to start and sustain vaccine administration. However, different PCPs perceive barriers to discussion in different ways. Interventions tailored to different groups of PCPs should assist them in overcoming barriers to discussing their recommendations when necessary.