OBJECTIVE: To project the health and economic consequences associated with a prophylactic type-specific HPV-16/18 vaccine in the setting of a cervical cancer screening program. METHODS: A computer-based model of the natural history of cervical cancer that incorporates the type-specific HPV distribution within precancerous lesions and cancer was used to estimate cancer incidence and mortality, quality-adjusted life years (QALY), lifetime costs, and incremental cost-effectiveness ratios associated with different cancer prevention policies consisting of vaccination, screening, and combined vaccination/screening strategies. Strategies included (1) no vaccination and no screening; (2) no vaccination and cytology screening every 1, 2, 3, 4, and 5 years; (3) vaccination and cytology screening every 1, 2, 3, 4, and 5 years. Screening strategies included conventional and liquid-based cytology initiated at ages 18, 21, 25, or 30. We assumed vaccination occurred at age 12 and was 90% effective in reducing the probability of acquiring persistent infection with HPV 16/18, but evaluated the impact of alternative assumptions about vaccine efficacy and waning immunity. RESULTS: Vaccination at age 12 followed by triennial cytology screening beginning at age 30 provided reductions in cervical cancer mortality above those provided by annual conventional cytology and had an incremental cost-effectiveness ratio of below $50,000 per QALY compared to the next best strategy of vaccination and triennial cytology screening beginning at age 35. These results were stable over a range of vaccine efficacies (60% to 100%) but sensitive to the degree to which vaccination effect persists over time. CONCLUSIONS: A prophylactic vaccine that prevents persistent HPV 16/18 infection can be expected to significantly reduce HPV-16/18-associated high-grade lesions and cervical cancer even in a setting of cytology screening. A program of vaccination that permits a later age of screening initiation and a less frequent screening interval is likely to be a cost-effective use of health care resources.