Though many studies have documented correlates of HPV vaccine acceptability, our study is one of the first to examine correlates of vaccine initiation. The current study aimed to identify modifiable correlates of HPV vaccine initiation among adolescent girls in high risk communities and whether correlates varied by race and urban/rural status. In 2007, we conducted a cross-sectional survey of 889 parents of adolescent girls aged 10–18 living in areas of North Carolina, USA with high cervical cancer rates. We analyzed data using logistic regression. Health Belief Model constructs were associated with HPV vaccine initiation in multivariate analyses, including doctor's recommendation to get HPV vaccine, perceived barriers to obtaining HPV vaccine, and perceived potential vaccine harms. While exploratory stratified analyses suggested that many of the same parent beliefs were important correlates of HPV vaccine initiation regardless of racial group or urban/rural status, a few differences did exist. These potentially modifiable beliefs offer well-defined targets for future interventions designed to increase HPV vaccine coverage. However, the beliefs' relative importance may differ between racial groups and regions.