Cytotoxic T Cells (CTLs) can exhibit considerable antitumor activity. Thus far, the characterized tumor peptide antigens recognized by CTLs are all presented by classical MHC class Ia molecules [human lymphocyte antigen A (HLA-A), HLA-B, and HLA-C in humans and H-2K, H-2D, and H-2L in mice]. Here we show that CTLs recognized peptides presented by nonclassical MHC class Ib molecule Qa-1b expressed by tumor cells. These CTLs conferred in vivo protection by delaying the growth of Qa-1b-expressing B78H1 melanoma cells pulsed with Qa-1b-binding peptides Cw4L or B35L and injected s.c. in C57BL/6 mice. A hierarchy of the peptides was found with regard to their ability to trigger CTLs; Cw4L stimulated a strong CTL response. The closely related and cross-reactive peptide B35L induced a weaker CTL response but was still efficient in sensitizing the target cells. Finally, Qa-1b-expressing melanoma cells without exogenous peptides were not immunogenic but possibly expressed endogenous cross-reactive antigenic peptides. The data are compatible with earlier findings that CTL activation requires relatively strong peptide antigens, whereas subsequent effector functions are also mediated by weak peptide analogues. In conclusion, CTLs mediated tumor immunity through the recognition of peptides presented by nonclassical MHC class Ib molecules. The identification of similar CTLs in humans may facilitate the vaccination of cancer patients because MHC class Ib/peptide complexes are much less polymorphic than MHC class Ia/peptide complexes.