Abstract Objectives Human papillomavirus (HPV) infections are highly prevalent sexually transmitted infections, notably associated with various cancers. This study analyses the health and economic impacts of HPV-associated diseases in the Czech Republic and evaluates the cost-effectiveness of a catch-up vaccination program. Methods Utilizing a Markov multistate model, the study assesses the lifetime impacts and costs related to HPV infections. Cohorts of ages 15–21 were simulated to assess the impact of catch-up vaccination outside the 11-year-old age group. Results The total quality-adjusted life years (QALYs) for the female and male cohorts (together 119,362 individuals) were higher in the vaccination scenario compared to the non-vaccination scenario. The increase in QALYs was 122,246 and 200,852 respectively, when considering the actual vaccination rates. Across both cohorts, 329 cancer-related deaths were prevented. In the probabilistic sensitivity analysis for the female population, vaccination was the dominant strategy in 99.3% of iterations. In the male population, vaccination was the dominant strategy in 80.3% of iterations. The implementation of catch-up vaccination for the 15–21 age group significantly increased QALY gains and reduced life-years-lost (LYLs). In the female cohort, all analysed rates of catch-up vaccination were the dominant strategy, while in the male cohort, the incremental cost-effectiveness ratios (ICERs) remained consistently below 42,000 CZK/QALY. Conclusions The catch-up vaccination program for 15-21-year-olds is cost-effective and can prevent a significant number of HPV-related cancers in both men and women.