The Health Belief Model (HBM) has been widely used as a framework to explain health behaviors in diverse populations, but little HBM research has focused on HIV-infected women and their increased risks for cervical cancer. We used Champion's Health Belief Model and Self-Efficacy scales to assess relationships between Pap test adherence and constructs of the HBM among 300 HIV-infected women. In addition, we assessed the relationship between HPV and cervical cancer knowledge and key HBM concepts. Participants reported low levels of knowledge regarding risk for cervical cancer and HPV. They perceived lower personal risk for cervical cancer. Women with higher perceived self-efficacy and lower perceived barrier scores reported better Pap test adherence. Findings indicate that HIV-infected women are not aware of the risk for cervical cancer and may not take preventive actions. Further research is needed to identify the full range of factors that impact adherence to cervical cancer screening.