OBJECTIVES: Existing cost-effectiveness analyses (CEAs) of Human Papillomavirus (HPV) vaccination assume cervical screening remains unchanged. However, current screening intensities are unlikely to be cost-effective due to the likely reduction in disease incidence in vaccinated women. Therefore, reductions in screening intensity are probable. The cost-effectiveness attributable to vaccination varies with screening intensity. The assumption of unaltered screening leads to an underestimation of vaccine cost-effectiveness relative to when screening intensity is reduced. Furthermore, failure to consider other screening intensities yields an incomplete efficient frontier in the cost-effectiveness plane. This can lead to an incorrect estimate of the price at which vaccination becomes marginally cost-effective for a given cost-effectiveness threshold. METHODS: We review cost-effectiveness estimates for a wide range of screening only and vaccination plus screening strategies from a model used to estimate vaccine cost-effectiveness in the Netherlands. We indicate what comparison was used to estimate vaccine cost-effectiveness in previous studies, show what comparisons would be more appropriate and explain how these differ. RESULTS: We then show why the cost-effectiveness of adding vaccination to a given screening strategy is not the appropriate basis to determine if the vaccine is cost-effective or the threshold price. Rather, both should be determined by the ICER between the most costly efficient screening only strategy and the least costly vaccination plus screening strategy, even where this least costly vaccination plus screening strategy is not the optimal strategy for a given threshold. CONCLUSIONS: CEAs of HPV vaccination may no longer be policy or research priorities following widespread reimbursement and precipitous price reductions. However, the methodological issues raised here are pertinent to both any future CEA of an enhanced vaccine with protection against more HPV types and more generally to cases in which the cost-effectiveness of complementary interventions are not independent.