There is growing interest in the association of radiotherapy and immunotherapy for the treatment of solid tumors. Here, we report an extremely effective combination of local irradiation (IR) and Shiga Toxin B (STxB)-based human papillomavirus (HPV) vaccination for the treatment of HPV-associated head and neck squamous cell carcinoma (HNSCC). The efficacy of the irradiation and vaccine association was tested using a model of HNSCC obtained by grafting TC-1/luciferase cells at a submucosal site of the inner lip of immunocompetent mice. Irradiation and the STxB-E7 vaccine acted synergistically with both single and fractionated irradiation schemes, resulting in complete tumor clearance in the majority of the treated mice. A dose threshold of 7.5 Gy was required to elicit the dramatic antitumor response. The combined treatment induced high levels of tumor-infiltrating, antigen-specific CD8(+) T cells, which were required to trigger the antitumor activity. Treatment with STxB-E7 and irradiation induced CD8(+) T-cell memory, which was sufficient to exert complete antitumor responses in both local recurrences and distant metastases. We also report for the first time that a combination therapy based on local irradiation and vaccination induces an increased pericyte coverage (as shown by αSMA and NG2 staining) and ICAM-1 expression on vessels. This was associated with enhanced intratumor vascular permeability that correlated with the antitumor response, suggesting that the combination therapy could also act through an increased accessibility for immune cells. The combination strategy proposed here offers a promising approach that could potentially be transferred into early-phase clinical trials.