A set of overlapping peptides corresponding to the L1, E6, and E7 proteins of human papilloma virus 16 was tested for their ability to bind to major histocompatibility complex class I molecules and to stimulate cytotoxic T-lymphocyte (CTL) responses in vitro. A class I binding assay using intact RMA-S cells showed that 20 of the 99 human papilloma virus peptides bound to H-2Kb and/or Db molecules. Fifteen of the 20 class I-binding peptides stimulated primary CTL responses, whereas peptides that were negative in the binding assay failed to do so. Peptide-induced CTLs recognized the immunizing peptide very efficiently, requiring no more than 1-10 nM peptide for target cell lysis. However, two observations were made that have important implications for the design of peptide-based vaccines for inducing CTLs. (i) Not all major histocompatibility complex-binding peptides that contained known motifs characteristic of naturally processed peptides induced CTLs. (ii) The efficiency of CTL lysis was strongly decreased when the size of the target peptide differed by only one amino acid residue from that of the immunizing peptide. We conclude that peptides chosen for vaccination must correspond in length to naturally processed peptides.