A new deterministic model for the transmission dynamics of human papillomavirus (HPV) and related cancers, in the presence of the Gardasil vaccine (which targets four HPV types), is presented. In the absence of routine vaccination in the community, the model is shown to undergo the phenomenon of backward bifurcation. This phenomenon, which has important consequences on the feasibility of effective disease control in the community, arises due to the re-infection of recovered individuals. For the special case when backward bifurcation does not occur, the disease-free equilibrium (DFE) of the model is shown to be globally-asymptotically stable (GAS) if the associated reproduction number is less than unity. The model with vaccination is also rigorously analyzed. Numerical simulations of the model with vaccination show that, with the assumed 90% efficacy of the Gardasil vaccine, the effective community-wide control of the four Gardasil-preventable HPV types is feasible if the Gardasil coverage rate is high enough (in the range 78–88%).