Human papillomavirus vaccine prevents infection by two major oncogenic types of the virus. Continued screening is needed in vaccinated women to prevent cancers caused by high-risk types not included in the vaccine. An exaggerated sense of protection from the vaccine could lead to a decline in the rate of screening among vaccinated women, which in principle could lead to an increase in the incidence of cervical cancer. We present a simple mathematical model of vaccination, screening, and disease incidence, including an analysis of the effect of data uncertainties. For a population with opportunistic screening and 30% vaccine coverage, screening rates in vaccinated women would have to decline by at least 80% (median value of probabilistic uncertainty analysis) before the incidence of cervical cancer would increase in the era since the introduction of the vaccine. By comparison, the decline needed is at least 49% in a population with organised screening and 70% vaccine coverage. In populations that have highly effective cervical screening programmes, incidence of cervical cancer starts to increase after smaller, but still substantial, decreases in screening. Introduction of vaccine is unlikely to lead to an increased incidence of cervical cancer as a result of diminished screening.