Objectives: The objective of this study was to simulate human papillomavirus (HPV) infection in a heterosexual population and subsequently analyze the incremental costs and effects of introducing a vaccination program against HPV types 6, 11, 16, and 18 in Denmark compared with screening alone. Methods: The analysis was performed in two phases. First, an agent-based transmission model was developed that described the HPV transmission without and with HPV vaccination. Second, an analysis of the incremental costs and effects was performed. The results of prevalence estimates of HPV, genital warts, cervical intraepithelial neoplasia (CIN1-3), and cervical cancer in the model simulations before and after introduction of HPV vaccination were extrapolated to the Danish population figures. Incremental costs and effects were then estimated. Future costs and effects were discounted. Results: Cost-effectiveness ratios for annual vaccination of 12-year-old girls, with a vaccination rate of 70 percent without a catch-up program, were estimated at approximately €1,917 per quality-adjusted life-year (QALY, 3 percent discount rate) and €10,846/QALY (5 percent discount rate), given a 62-year time horizon. Conclusions: A vaccination program would incur extra vaccination costs but would save treatment costs and improve both quality of life and survival.