New and upcoming vaccines provide protection against types 16 and 18 of human papillomavirus (HPV), which are responsible for an estimated 70% of all cervical cancers. One vaccine also protects against HPV types 6 and 11, which cause more than 90% of genital warts. We use a mathematical model of HPV transmission and immunity to explore the effect of vaccination on the evolution of HPV types. If vaccination provides cross-immunity at least equal to that of natural infection, it may contract the niche space available to other HPV types a million-fold. If natural infection provides greater cross-immunity than vaccination, vaccination may expand available niche space up to 470-fold. The balance of epidemiologic data suggests vaccination will reduce the available niche space.