Most cervical carcinoma (Cxca) cells constitutively express human papillomavirus type 16 (HPV16) E6 and E7 oncoproteins. These proteins are, therefore, attractive targets for T cell-based immunotherapy. Previously, we identified HVP16 E7-encoded CTL epitopes. In patients with cervical intraepithelial neoplasia or Cxca, little is known concerning T-cell activity against viruses in general and against HPV16 in particular. Here, we have screened the blood of 10 healthy donor controls and of 22 patients with HPV16+ cervical lesions for the presence of CTLs directed against HPV16 E7- and control influenza virus matrix-derived epitopes presented by HLA-A *0201. We detected influenza virus-specific CTLs in all donors and in the majority of patients, indicating that most patients have functioning T-cell responses despite their lesions or therapeutic interventions. Moreover, we show that patients with HPV16+ lesions occasionally have memory CTLs against a HPV16 E7-encoded epitope (sequence YMLD-LQPETT), providing evidence for natural CTL immunity against HPV16 in patients with cervical lesions. Combined, these findings raise possibilities for vaccination with HPV16 E7-encoded peptides to induce or augment CTL responses for treatment or prevention of Cxca.