OBJECTIVE: To determine the potential effects on costs and outcomes of changes in sensitivity and specificity with new screening methods for cervical cancer. METHODS: Using a Markov model of the natural history of cervical cancer, we estimated the effects of sensitivity, specificity, and screening frequency on cost-effectiveness. Our estimates of conventional Papanicolaou test sensitivity of 51% and specificity of 97% were obtained from a meta-analysis. We estimated the effect of reducing false-negative rates from 40-90% and increasing false-positive rates by up to 20%, independently and jointly. We varied the marginal cost of improving sensitivity from $0 to $15. RESULTS: When specificity was held constant, increasing sensitivity of the Papanicolaou test increased life expectancy and costs. When sensitivity was held constant, decreasing specificity of the Papanicolaou test increased costs, an effect that was more dramatic at more frequent intervals. Decreased specificity had a substantial effect on cost-effectiveness estimates of improved Papanicolaou test sensitivity. Most of those effects are related to the cost of evaluation and treatment of low-grade lesions. CONCLUSION: Policies or technologies that increased sensitivity of cervical cytologic screening increased overall costs, even if the cost of the technology was identical to that of conventional Papanicolaou smears. These effects appear to be caused by relatively high prevalence of low-grade lesions and are magnified at frequent screening intervals. Efficient cervical cancer screening requires methods with greater ability to detect lesions that are most likely to become cancerous.