Background: HIV-infected women are at increased risk for developing cervical cancer. Women living in resource-limited countries are especially at risk due to poor access to cervical cancer screening and treatment. We evaluated three cervical cancer screening methods to detect cervical intraepithelial neoplasia grade 2 and above (CIN 2+) in HIV-infected women in South Africa; Pap smear, visual inspection with 5% acetic acid (VIA) and human papillomavirus detection (HPV). Methods: HIV-infected women aged 18–65 were recruited in Johannesburg. A cross-sectional study evaluating three screening methods for the detection of the histologically-defined gold standard CIN-2 + was performed. Women were screened for cervical abnormalities with the Digene HC2 assay (HPV), Pap smear and VIA. VIA was performed by clinic nurses, digital photographs taken and then later reviewed by specialist physicians. The sensitivity, specificity and predictive valves for CIN-2 + were calculated using maximum likelihood estimators. Results: 1,202 HIV-infected women participated, with a median age of 38 years and CD4 counts of 394 cells/mm3. One third of women had a high grade lesion on cytology. VIA and HPV were positive in 45% and 61% of women respectively. Estimated sensitivity/specificity for HPV, Pap smear and VIA for CIN 2+ was 92%/51.4%, 75.8%/83.4% and 65.4/68.5% (nurse reading), respectively. Sensitivities were similar, and specificities appeared significantly lower for the HPV test, cytology and VIA among women with CD4 counts ≤200 cells/mm3 as compared to CD4 counts >350 cells/mm3. Conclusions: Although HPV was the most sensitive screening method for detecting CIN 2+, it was less specific than conventional cytology and VIA with digital imaging review. Screening programs may need to be individualized in context of the resources and capacity in each area.