Background: In 2009, both Norway and Denmark initiated routine quadrivalent human papillomavirus vaccination (qHPV) for 12-year-old girls; however, Denmark also introduced free-of-charge multi-cohort vaccination for older age groups in 2008. We aim to describe trends in genital warts (GWs) incidence rates (IRs) among men and women and qHPV vaccine coverage among women in Norway and Denmark in 2006–2015. Methods: We linked multiple national health registries in Norway and Denmark via national personal identifiers to access data on GWs incidence and qHPV vaccination among women and men aged 12–35 years residing in Norway and Denmark in 2006–2015. We calculated age-specific and age-standardized GWs IRs, GWs IR trends before (2006–2009) and after (2009–2015) the implementation of qHPV vaccination, and qHPV vaccine coverage among women. Results: In Norway and Denmark together, there were more than 200,000 cases of incident GWs and over 710,000 girls got at least one dose of qHPV vaccine during the study period. The total qHPV coverage in Norway and Denmark in 2015 was among women aged 12–35 years 24% and 70%, respectively. GWs IRs in Norway and Denmark decreased annually in 2009–2015 among women by 4.8% (95% confidence interval: 4.3 to 5.3) and 18.0% (95%CI: 17.5 to 18.6), respectively, and among men 1.9% (95%CI: 1.4 to 2.4) and 10.7% (95%CI: 10.3 to 11.2), respectively. In Denmark, GWs IRs decreased rapidly among both sexes and all age groups after qHPV vaccination, while Norway showed only a modest decrease. Conclusion: Rapid decline in HPV-related morbidity is feasible with high coverage of multi-cohort vaccination. However, the decision to vaccinate a single cohort of 12-years-old girls only will postpone HPV-related disease control by at least a decade. Thus countries planning HPV vaccination programs should also initiate multi-cohort vaccination for faster disease control.