PURPOSE: With several HPV candidate vaccines in phase 3 clinical trials, decision analytic models capable of simultaneously reflecting population infection dynamics as well as clinical disease in individuals are being developed. We conducted an exploratory analysis using a Markov cohort model to identify key parameters with potential impact on the cost-effectiveness of HPV 16/18 vaccination. METHOD(S): We calibrated a computer-based model that simulates the natural history of cervical cancer to country-specific data from sub-Saharan Africa on age-specific prevalence of HPV, precancerous lesions, age-specific incidence of cancer, and type-distribution of HPV types with lesions and cancer. We estimated lifetime costs (2002 International Dollars), life expectancy, and cost-effectiveness ratios for three strategies: (1) vaccination alone; (2) screening alone using HPV DNA testing or cervical cytology once in a lifetime in the mid-30s, and (3) vaccination plus screening. Direct medical and non-medical costs were derived from primary cost data collected in Tanzania, and vaccine delivery cost estimation tools from the WHO. Assumptions related to population coverage, vaccine efficacy and waning, and screening performance were explored. RESULTS: In the most optimistic vaccine scenario evaluated (100% coverage, 90% effective, no waning), the lifetime risk of cervical cancer was reduced by nearly 60% with HPV16/18 vaccination in early adolescence; 12-43% by screening depending on modality and frequency; and 66-80% by combination vaccination and screening. Cost-effective strategies included vaccination alone, and combination of vaccination and screening with visual inspection with acetic acid or HPV DNA testing once per lifetime. Results were most sensitive to vaccination coverage, cost of administering the vaccine, and the duration of protection. CONCLUSIONS: Results from this exploratory analysis suggest that HPV vaccination of young girls in Tanzania may be promising, especially when combined with a single-lifetime screening in older women.