High-risk human papillomavirus (HPV) encoding E6/E7-HPV oncogenes are responsible for a subgroup of head and neck squamous-cell carcinoma (HNSCC) and thus therapeutic E7-vaccines may be used to control HPV+HNSCC tumors. Herein we investigated the effects of an optimized nanoparticle-conjugated E7 long-peptide vaccine adjuvanted with CpG (NP-E7LP) in an orthotopic immunocompetent mouse model of HPV+HNSCC which is based on injection of HPV16 E6/E7-expressing mEERL95-cells into the submental space. In absence of surgery, vaccination performed before or after tumor-cell injection decreased tumor growth or prolonged mice survival only marginally, despite the high numbers of vaccine-induced circulating E7-specific IFN-gamma-secreting CD8(+) T-cells. This contrasts with the high-efficacy of NP-E7LP-vaccination reported in the genital and subcutaneous HPV16-E6/E7-expressing TC-1 models. Our data show that in a direct comparison, NP-E7LP-vaccination fully controlled TC-1, but not mEERL95, tumors subcutaneously growing in the flanks. Immune-cell infiltration was 10-fold higher in TC-1-tumors, than in mEERL95-tumors, suggesting that vaccine-induced CD8(+) T-cells can only poorly infiltrate mEERL95-tumors. Indeed, immunofluorescence staining of orthotopic mEERL95-tumors showed that CD3(+) T-cells are preferentially located peritumorally. However, when NP-E7LP-vaccination was performed after mEERL95-cell injection, but before resection of primary tumors, no postsurgical recurrence was observed and 100% of the mice survived until the experimental endpoint (day 70) in the NP-E7LP-vaccinated group. In contrast, we observed a 60% recurrence rate and only 35% survival in PBS-vaccinated mice. This suggests that removal of the primary tumor modified the tumor microenvironment, allowing a therapeutic effect of the vaccine-induced anti-tumor response. E7-vaccination combined with surgery may thus benefit patients with HPV+HNSCC.