The cost and cost effectiveness of screening previously unscreened women by VIA, cytology or HPV testing was investigated within a large cluster randomised trial involving 131,178 women in rural India. All resources involved in implementation, training, management, recruitment, screening and diagnosis were identified and costed. We estimated the total costs and detection rates for each cluster and used these data to calculate an average cluster cost and detection rate for each screening approach. These estimates were combined to estimate a cost per case of cervical intraepithelial neoplasia grade 2/3 or invasive cancer (CIN 2/3+) detected. The average total costs per 1,000 women eligible for screening were US dollar 3,917, US dollar 6,609 and US dollar 11,779 with VIA, cytology and HPV respectively. The cost of detecting a case of CIN2/3+ using VIA was dollar 522 (95% CI dollar 429- dollar 652). Our results suggest that more CIN2/3+ cases would be detected in the same population if cytology were used instead of VIA and each additional case would cost US dollar 1065 (95% CI dollar 713- dollar2175). Delivering cervical cancer screening is potentially expensive in a low-income country although costs might be lower outside a trial setting. We found screening with VIA to be the least expensive option, but it also detected fewer cases of CIN2/3+ than other methods; its long-term cost-effectiveness will depend on the long-term benefits of early detection. Cytology was more effective at detecting cases than VIA but was also more expensive. Our findings indicate that HPV may not be a cost effective screening strategy in India at current consumable prices.