Objective: To identify barriers to cervical cancer screening and treatment, and determine acceptance toward peer navigators (PNs) to reduce barriers. Methods: A cross-sectional study was conducted among women with HIV infection aged 19 years or older attending HIV clinics in Dar es Salaam, Tanzania, between May and August 2012. Data for sociodemographic characteristics, barriers, knowledge and attitude toward cervical cancer screening and treatment, and PNs were collected by questionnaire. Results: Among 399 participants, only 36 (9.0%) reported previous cervical cancer screening. A higher percentage of screened than unscreened women reported being told about screening by someone at the clinic (25/36 [69.4%] vs 132/363 [36.4%]; P=0.002), knew that screening was free (30/36 [83.3%] vs 161/363 [44.4%]; P<0.001), and obtained “good” cervical screening attitude scores (17/36 [47.2%] vs 66/363 [18.2%]; P=0.001). Most women (382/399 [95.7%]) did not know about PNs. When told about PNs, 388 (97.5%) of 398 women said they would like assistance with explanation of medical terms, and 352 (88.2%) of 399 said they would like PNs to accompany them for cervical evaluation and/or treatment. Conclusion: Use of PNs was highly acceptable and represents a novel approach to addressing barriers to cervical cancer screening and treatment.