Poor oral health is common in HIV+ adults. We explored the feasibility, acceptance, and key features of a prevention-focused oral health education program for HIV+ adults. This was a pilot substudy of a parent study in which all subjects (n = 112) received a baseline periodontal disease (PD) examination and provider-delivered oral health messages informed by the Information-Motivation-Behavioral Skills (IMB) Model. Forty-one parent study subjects were then eligible for the substudy; of these subjects, a volunteer sample was contacted and interviewed 3-6 months after the baseline visit. At the recall visit, subjects self-reported behavior changes that they had made since the baseline. PD was reassessed using standard clinical assessment guidelines, and results were shared with each subject. At recall, individualized, hands-on oral hygiene coaching was performed and patients provided feedback on this experience. Statistics included frequency distributions, means, and chi-square testing for bivariate analyses. Twenty-two HIV+ adults completed the study. At recall, subjects had modest, but nonsignificant (p > 0.05) clinician-observed improvement in PD. Each subject reported adopting, on average, 3.8 (± 1.5) specific oral health behavior changes at recall. By self-report, subjects attributed most behavior changes (95%) to baseline health messages. Behavior changes were self-reported for increased frequency of flossing (55%) and toothbrushing (50%), enhanced toothbrushing technique (50%), and improved eating habits (32%). As compared to smokers, nonsmokers reported being more optimistic about their oral health (p = 0.024) at recall and were more likely to have reported changing their oral health behaviors (p = 0.009). All subjects self-reported increased knowledge after receiving hands-on oral hygiene coaching performed at the recall visit. In HIV+ adults, IMB-informed oral health messages promoted self-reported behavior change, subjects preferred more interactive, hands-on coaching. We describe a holistic clinical behavior change approach that may provide a helpful framework when creating more rigorously designed IMB-informed studies on this topic.