The human papillomavirus (HPV) vaccines hold great promise for preventing several cancers caused by HPV infections. Yet, little attention has been given to whether HPV could respond evolutionarily to the new selection pressures imposed on it by the novel immunity response created by the vaccine. Here, we present and theoretically validate a mechanism by which the vaccine alters the Transmission-Recovery trade-off that constrains HPV’s virulence such that higher oncogene expression is favoured. With a high oncogene expression strategy the virus is able to increase its viral load and infected cell population before clearance by the vaccine, thus improving its chances of transmission. This new rapid cell-proliferation strategy is able to circulate between hosts with medium-to-high turnover rates of sexual partners. We also discuss the importance of better quantifying the duration of challenge infections and the degree to which a vaccinated host can shed virus. The generality of the models presented here suggests a wider applicability of this mechanism and thus, highlights the need to investigate viral oncogenicity from an evolutionary perspective.