In 1986, Kärre and colleagues reported that natural killer (NK) cells rejected an MHC class I-deficient tumor cell line (RMA-S) but they did not reject the same cell line if it expressed MHC class I (RMA). Based on this observation, they proposed the concept that NK cells provide immune surveillance for "missing self," e.g., they eliminate cells that have lost class I MHC antigens. This seminal observation predicted the existence of inhibitory NK cell receptors for MHC class I. Here, we present evidence that NK cells are able to reject tumors expressing MHC class I if the tumor expresses a ligand for NKG2D. Mock-transfected RMA cells resulted in tumor formation. In contrast, when RMA cells were transfected with the retinoic acid early inducible gene-1 gamma or delta (RAE-1), ligands for the activating receptor NKG2D, the tumors were rejected. The tumor rejection was mediated by NK cells, and not by CD1-restricted NK1.1(+) T cells. No T cell-mediated immunological memory against the parental tumor was generated in the animals that had rejected the RAE-1 transfected tumors, which succumbed to rechallenge with the parental RMA tumor. Therefore, NK cells are able to reject a tumor expressing RAE-1 molecules, despite expression of self MHC class I on the tumor, demonstrating the potential for NK cells to participate in immunity against class I-bearing malignancies.