Persistent infection by 'high risk' genotypes of human papilloma virus (HPV) is necessary but not sufficient for the development of over 98% of cervical cancers. Thus the development of vaccines that prevent HPV transmission represent an important opportunity to prevent cervical cancer. There are several prophylactic HPV vaccine formulations based upon L1 virus-like particles (VLPs) currently in phase III trials and recently released data are extremely promising. However, many practical issues surrounding implementation of these vaccines need to be addressed including, who and when to vaccinate, duration of protection, and integration with current screening programs. The vaccines currently being evaluated target the two most prevalent high risk HPV types which are responsible for approximately 70% of cervical cancers. To increase the breadth of protection, it is likely that L1 VLPs of other viral subtypes must be included, although vaccines targeting the conserved regions of the L2 minor capsid protein warrant further exploration in this regard. In addition the vaccines nearing licensing will not combat established HPV-related disease and a therapeutic vaccine, of which there are several candidates in early stages of development, would be desirable. This review discusses the background to and progress in vaccine development and the issues surrounding the introduction of HPV vaccines.