Recent trials have indicated that women with prior exposure to Human papillomavirus (HPV) subtypes 16/18 receive protection against reinfection from the HPV vaccines. However, many of the original models investigating the cost effectiveness of different vaccination strategies for the protection of cervical cancer assumed, based on the trial results at that time, that these women received no protection. We developed a deterministic, dynamic transmission model that incorporates the vaccine-induced protection of women with prior exposure to HPV. The model was used to estimate the cost effectiveness of progressively extending a vaccination programme using the bivalent vaccine to older age groups both with and without protection of women with prior exposure. We did this under a range of assumptions on the level of natural immunity. Our modelling projections indicate that including the protection of women with prior HPV exposure can have a profound effect on the cost effectiveness of vaccinating adults. The impact of this protection is inversely related to the level of natural immunity. Our results indicate that adult vaccination strategies should potentially be reassessed, and that it is important to include the protection of non-naive women previously infected with HPV in future studies. Furthermore, they also highlight the need for a more thorough investigation of this protection.