BACKGROUND: While many studies have compared the efficacy of Pap cytology, visual inspection with acetic acid (VIA) and human papillomavirus (HPV) DNA assays for the detection cervical intraepithelial neoplasia and cancer, few have evaluated the program effectiveness. METHODS AND FINDINGS: A population-based sample of 5603 women from Medchal Mandal in Andhra Pradesh, India were invited to participate in a study comparing Pap cytology, VIA, and HPV DNA screening for the detection of CIN3+. Participation in primary screening and all subsequent follow-up visits was rigorously tracked. A 20% random sample of all women screened, in addition to all women with a positive screening test result underwent colposcopy with directed biopsy for final diagnosis. Sensitivity, specificity, positive and negative predictive values were adjusted for verification bias. HPV testing had a higher sensitivity (100%) and specificity (90.6%) compared to Pap cytology (sensitivity  =  78.2%; specificity = 86.0%) and VIA (sensitivity = 31.6%; specificity = 87.5%). Since 58% of the sample refused involvement and another 28% refused colposcopy or biopsy, we estimated that potentially 87.6% of the total underlying cases of CIN3 and cancer may have been missed due to program failures. CONCLUSIONS: We conclude that despite our use of available resources, infrastructure, and guidelines for cervical cancer screening implementation in resource limited areas, community participation and non-compliance remain the major obstacles to successful reduction in cervical cancer mortality in this Indian population. HPV DNA testing was both more sensitive and specific than Pap cytology and VIA. The use of a less invasive and more user-friendly primary screening strategy (such as self-collected swabs for HPV DNA testing) may be required to achieve the coverage necessary for effective reduction in cervical cancer mortality.