Human Papilloma Virus (HPV)-induced (pre-)malignancies offer an excellent case for the rational design of immunotherapeutic strategies against cancer. Transformed cells express tumor-specific antigens of viral origin while the spontaneous antitumor response and the immunological make up of HPV-induced tumors do not differ from other immunogenic epithelial tumors. A first clinically active therapeutic HPV vaccine has been developed and clear links were found between the type and kinetics of vaccine-induced T-cell immunity. Here, we will review the mechanisms determining the success and failure of therapeutic vaccines against HPV-induced tumors, with particular emphasis on the immunological setting in which these vaccines need to work. The recent progress in therapeutic HPV vaccination will guide the development of successful vaccines in other diseases.