Despite recommendations for vaccination against hepatitis A (HAV) of men who have sex with men (MSM), most remain unvaccinated. This study was designed to identify attitudes and beliefs associated with vaccination against HAV using a conventional outreach sample of African American MSM in Birmingham, Alabama. Of 107 participants, nearly 34% reported being vaccinated against HAV. Over half of the participants reported 10 or more different lifetime male sexual partners, and a third reported having had intercourse with females, as well as, males within the past 5 years. About 10% of the participants reported condom use over half of the time during oral intercourse, and 50% of the participants reported using a condom over half the time during anal intercourse. In multivariable analysis, predictors of HAV vaccination were a decreased perception of the practical barriers to HAV vaccination (odds ratio [OR], 0.05; 95% confidence interval [CI]: 0.01-0.18, P = 0.002); increased health provider communication (OR, 9.89; 95% CI: 2.74-35.65, P = 0.02); and increased perceived personal self-efficacy to complete the two-dose series (OR, 7.31; 95% CI: 2.38-22.45, P = 0.02). Our findings underscore the need to increase vaccination through innovative approaches to reduce perceived barriers to vaccination while increasing provider-patient communication and self-efficacy to complete the vaccine series.