Context: Recently published results suggest that effective vaccines against cervical cancer-associated human papillomavirus (HPV) may become available within the next decade. Objective: To examine the potential health and economic effects of an HPV vaccine in a setting of existing screening. Design, Setting, and Population: A Markov model was used to estimate the lifetime (age 12-85 years) costs and life expectancy of a hypothetical cohort of women screened for cervical cancer in the United States. Three strategies were compared: (1) vaccination only; (2) conventional cytological screening only; and (3) vaccination followed by screening. Two of the strategies incorporated a vaccine targeted against a defined proportion of high-risk (oncogenic) HPV types. Screening intervals of 1, 2, 3, and 5 years and starting ages for screening of 18, 22, 24, 26, and 30 years were chosen for 2 of the strategies (conventional cytological screening only and vaccination followed by screening). Main Outcome Measures: Incremental cost per life-year gained. Results: Vaccination only or adding vaccination to screening conducted every 3 and 5 years was not cost-effective. However, at more frequent screening intervals, strategies combining vaccination and screening were preferred. Vaccination plus biennial screening delayed until age 24 years had the most attractive cost-effectiveness ratio ($44889) compared with screening only beginning at age 18 years and conducted every 3 years. However, the strategy of vaccination with annual screening beginning at age 18 years had the largest overall reduction in cancer incidence and mortality at a cost of $236250 per life-year gained compared with vaccination and annual screening beginning at age 22 years. The cost-effectiveness of vaccination plus delayed screening was highly sensitive to age of vaccination, duration of vaccine efficacy, and cost of vaccination. Conclusions: Vaccination for HPV in combination with screening can be a cost-effective health intervention, but it depends on maintaining effectiveness during the ages of peak oncogenic HPV incidence. Identifying the optimal age for vaccination should be a top research priority.