Background Denmark is one of the countries where Human papillomavirus (HPV)-vaccination at present includes only girls. However, the burden of HPV-related cancer in men is increasing, which would argue for gender-neutral vaccination. The aim of this study was to examine the burden of HPV-caused cancers in women and men, and to evaluate the potential of HPV-vaccination in cancer control. Methods Data were retrieved from the literature on population prevalence of high risk (HR) HPV, on HR HPV-prevalence and genotypes in HPV-related cancers, and on number of cytology samples in cervical screening. Data on annual biopsies and conisations were retrieved from the Danish National Health Service Register and the Danish National Patient Register. Incidences of HPV-related cancers in Denmark were extracted from NORDCAN. Number of HPV-caused cancers was calculated from number of HPV-related cancers and the proportion known to be caused by high-risk (HR) HPV. Results In cross-sectional surveys in Denmark, one fifth of women and almost one third of men were found to be positive for HR HPV. Per year, 548 HPV-caused cancer cases were diagnosed in women and 234 in men, and twice as many cancers in women as in men were preventable with HPV vaccination. However, including screening prevented cervical cancers, the burden of cancers caused by HPV-infection would be 1300–2000 in women as compared to 234 in men. Conclusion Taking screening prevented cervical cancers into account, the cancer control potential of HPV-vaccination is considerably higher in women than in men. HPV-vaccination could reduce the burden of screening on women and on health care resources.