OBJECTIVES: As antiretroviral therapy is scaled up in Africa, HIV-positive women are increasingly likely to die from cervical cancer, a leading cause of cancer death. Effective screens for cervical cancer exist including Papanicolaou smear (Pap), visual inspection of the cervix with acetic acid (VIA), and human papillomavirus testing (HPV). Our objective was to prospectively assess cost-effectiveness of cervical cancer screening methods for HIV-positive women. METHODS: The analysis was based on data from 500 HIV-positive women who underwent VIA, Pap, HPV, and gold-standard colposcopy-directed biopsy in Nairobi, Kenya. A Markov model projected life expectancy and costs for six cervical screening strategies: Pap; VIA; HPV; testing positive for both VIA+Pap, Pap+HPV, VIA+HPV.  Cost-effectiveness was calculated for overall population and by CD4 count. Strategies were compared using an incremental cost-effectiveness ratio (ICER)--the additional cost per life year (LY) gained. Impact of parameter uncertainty was addressed using univariate and probabilistic multivariate sensitivity analysis. RESULTS: VIA had lowest cost and highest life expectancy ($331, 17.2 LYs), followed by HPV ($569, 17.1 LYs), Pap ($622, 17.1 LYs), HPV+Pap ($836, 17.0 LYs), VIA+HPV ($857, 17.0 LYs), and VIA+Pap ($897, 17.0 LYs). CD4 level did not affect this rank order, though VIA at low CD4 showed the lowest cost ($111, 15.3 LY), while VIA at high CD4 produced most health gains ($285, 19.9 LY) [ICER: $37/LY]. Costs were sensitive to prevalence of cancer, sensitivity, age, and cost of cancer. Life expectancy was sensitive to age at screening. Results were robust to probabilistic sensitivity analysis. CONCLUSIONS: VIA is projected to be the most cost-effective screening strategy for cervical cancer among HIV-positive women. This is due to its high sensitivity, low screening cost, low risk treatment, and high cervical cancer cost. Screening women with high CD4 is particularly cost-effective. VIA should be implemented among HIV-positive women in low-income settings.