OBJECTIVES: To assess the cost-effectiveness of various cervical screening strategies in a cohort of 12-year-old US women with (V) and without (NV) a human papillomavirus (HPV) 16/18 vaccine with efficacy against vaccine and non-vaccine oncogenic HPV types. METHODS: A lifetime Markov model simulating the progression of HPV infection and subsequent cervical disease (cervical intraepithelial neoplasia (CIN), cervical cancer, and death) was developed. Thirty cervical screening strategies were investigated, including the American College of Obstetricians and Gynecologists’ recommendation: screening women every 2 years starting at age 21 years, increasing to 3 years following three consecutive negative tests after age 29 (denoted “21/2-3”).  Other strategies varied initial screening age (16, 21, or 25 years) and screening frequency before and after age 30 years (every 1, 2, 3, 4, or 5 years). Vaccination was assumed to provide 95% efficacy against CIN2+ due to types 16/18 and 37.4% efficacy against CIN2+ excluding co-infections due to HPV types 16/18 (extrapolated to efficacy against infection). The primary outcome was incremental cost-effectiveness ratio (ICER) per quality-adjusted life-year (QALY) gained.  Full screening compliance and vaccination coverage were assumed; all outcomes discounted at 3% per year. RESULTS: The 25/5-5NV strategy (every 5 years starting at age 25 years, without vaccination) was least costly. No other screening scenario without vaccination was cost-effective. The 25/5-5V strategy was cost-effective compared with the 25/5-5NV strategy ($9,000/QALY). Other non-dominated strategies (25/3-4V, 25/2-3V, and 25/1-2V) produced ICERs above $100,000 per QALY.  CONCLUSIONS: Model results suggest initiating screening at age 25 with a 5-year frequency  in the presence of HPV vaccination is cost-effective compared with increasing screening frequency without vaccination or lowering the age of screening initiation.  Increasing HPV vaccination in 12-year-old women would allow for less frequent screening initiated at older ages, constituting an efficient use of healthcare resources.