Human Papilloma Viruses (HPVs) are the most common sexually transmitted agents worldwide, and chronic infection with oncogenic HPVs can lead to the development of lesions in the cervix, the vulva, and the head and neck region. In some patients, these lesions will eventually progress to squamous cell carcinomas that have the potential to spread to distant sites. Cervical cancer is by far the most common type of HPV-related malignancy, and at the early stages can be treated quite effectively. However, for patients in the later stages of tumor progression traditional therapeutic approaches like chemotherapy are poorly effective, and the development of novel strategies based on immunotherapy is undergoing. Clinical trials using HPV E6/E7-derived synthetic long peptides (SLPs) vaccines have shown promising results. However, these vaccines are only leading to significant responses in a low percentage of patients bearing pre-malignant lesions, whereas they seem to be completely ineffective in patients with advanced tumors, suggesting the presence of immune-escape mechanisms. Here I describe an improved therapeutic vaccination approach based on conjugation of E7-derived SLPs to solid-phase ultra-small (30 nm in diameter) nanoparticles (NPs). The NP-conjugated formulation (NP-E7LP) was able to significantly enhance both the systemic and local anti-tumor immune responses, leading to higher CD8 T cell infiltrates in the tumor microenvironment (TME) resulting in a significant reduction in tumor burden and overall increased survival in mice bearing transplantable HPV+ TC1 and SC1 tumors. Next, I demonstrate that a transgenic mouse model for HPV-related cancers expressing the HPV16 early region under the keratin 14 promoter bears striking similarities to cervical cancer patients regarding the alteration of the immune system provoked by HPVs. By taking advantage of the K14HPV16 H2b model, I show that the use of a nanoparticle-conjugated vaccine is required to elicit an immune response, but that, similarly to cervical cancer patients, therapeutic vaccination alone is not sufficient to elicit efficacious anti-tumor immunity. I also illustrate that combinatorial trials involving several different therapeutic antibodies are not sufficient to significantly boost the anti-tumor immune response. Finally, I identify a substantial increase in immunosuppressive myeloid cells (MDSCs) as the mechanism likely responsible for the observed impairment of the immune response, a feature that seems to be shared by cervical cancer patients. Interestingly, 5 although the attention of most of the researchers in the field is usually focused on the TME, I provide evidence that this myeloid cell-dependent mechanism is acting upstream in the lymphoid organs where it inhibits the very first steps in the generation of the anti-tumor immune response. My data suggest that this mechanism could potentially put an early stop to the cancer-immunity cycle, thereby contributing to the ineffectiveness of immunotherapies in cervical cancer patients. In summary, this thesis provides new knowledge that will contribute to the improvement of immunotherapy-based approaches against cervical cancer and other HPV-related diseases with the potential for applicability to other types of cancer.