Cervical cancer, the second leading cause of cancer mortality in women worldwide, results from infection with a subset of human papillomaviruses (HPV), HPV-16 being the most prevalent type. The available prophylactic vaccines are an effective strategy to prevent this cancer in the long term. However, they only target 70-80% of all cervical cancers and cannot control existing HPV infections and associated lesions. Therapeutic vaccines are thus necessary for women who cannot benefit from prophylactic vaccination. Induction of protective immune responses in the genital mucosa (GM) may be crucial for efficacy of HPV therapeutic vaccines. We report here that mice that received a single subcutaneous (s.c.) vaccination of an adjuvanted long synthetic HPV16 E7(1-98) polypeptide showed induction of 100% tumor protection against s.c. TC-1 tumors and that tumor regression was mainly provided by CD8 T cells. In vivo cytotoxic assay revealed high E7-specific cytolytic T lymphocytes activity in spleen and in genital draining lymph nodes (LN), and E7-specific CD8 T cells could be detected in GM by tetramer staining. More importantly, high-avidity E7-specific INF-gamma secreting CD8 T cells were induced not only in blood, spleen and LN but also in GM of vaccinated mice, thus providing evidence that a parenteral vaccination may be sufficient to provide regression of genital tumors. In addition, there was no correlation between the responses measured in blood with those measured in GM, highlighting the necessity and relevance to determine the immune responses in the mucosa where HPV-tumors reside.