Objective: To examine the cost-effectiveness of introducing an HPV-16/18 prophylactic cervical cancer (CC) vaccine in a setting of existing screening in Portugal. Methods: A Markov cohort simulation model was used with an annual cycle length and which mimics the natural history of HPV infection to CC. The analysis was undertaken from the health care system perspective. Direct medical costs were estimated and discounted at a rate of 3%. Effect measures were: CC cases and deaths avoided, life years saved and QALYs, discounted at a rate of 3%. The incremental cost-effectiveness was estimated by comparison of the options to be implemented with the current strategy. The analytic horizon was lifetime where subjects enter the model at 10 years old and are followed for 95 cycles until death. One-way sensitivity analysis was conducted on the key variables. Results: Our results predicted that an HPV-16/18 vaccine targeting 12-year-old girls would be cost-effective and could reduce life-time CC cases and mortality by 92% compared with current screening. Vaccination was predicted to substantially reduce the number of oncogenic HPV infections and Cervical Intraepithelial Neoplasia cases (CIN1-3 cases). The additional cost of generating one QALY by implementing a vaccination strategy, where all 12-year-old girls are vaccinated with a vaccine showing 96.7% efficacy against HPV-16/18, was €13,810. The results were sensitive to alternative assumptions about the discount rate and age at which vaccination begins. The base-case strategy was robust to modifications in vaccination coverage and fairly robust to changes in both percentages of oncogenic HPV and of opportunistic screening rates. Conclusion: The analysis suggested that prophylactic cervical cancer vaccination could have a substantial public health benefit. A vaccine directed specifically at reducing the incidence of oncogenic HPV types 16 and 18, during the peak ages of infection, could be expected to be economically attractive.