One half of a group of 20 patients with human papillomavirus type 16 (HPV16)-induced vulvar intraepithelial neoplasia grade 3 displayed a complete regression (CR) after therapeutic vaccination with HPV16 E6/E7 synthetic long peptides. Patients with relatively larger lesions generally did not display a CR. To investigate immune correlates of treatment failure, patients were grouped according to median lesion size at study entry, and HPV16-specific immunity was analyzed at different time points by complementary immunological assays. The group of patients with smaller lesions displayed stronger and broader vaccine-prompted HPV16-specific proliferative responses with higher IFNγ (P = 0.0003) and IL-5 (P < 0.0001) levels than patients with large lesions. Characteristically, this response was accompanied by a distinct peak in cytokine levels after the first vaccination. In contrast, the patient group with larger lesions mounted higher frequencies of HPV16-specific CD4⁺CD25⁺Foxp3⁺ T cells (P = 0.005) and displayed a lower HPV16-specific IFNγ/IL-10 ratio after vaccination (P < 0.01). No disparity in T memory immunity to control antigens was found, indicating that the differences in HPV-specific immunity did not reflect general immune failure. We observed a strong correlation between a defined set of vaccine-prompted specific immune responses and the clinical efficacy of therapeutic vaccination. Notably, a high ratio of HPV16-specific vaccine-prompted effector T cells to HPV16-specific CD4⁺CD25⁺Foxp3⁺ T cells was predictive of clinical success. Foxp3⁺ T cells have been associated previously with impaired immunity in malignancies. Here we demonstrate that the vaccine-prompted level of this population is associated with early treatment failure.