Cancer vaccines used to generate specific cytotoxic T lymphocytes are not effective against tumor cells that have lost or suppressed expression of their class I major histocompatibility complex proteins. This loss is common in some cancers and particularly in metastatic lesions. We show that β₂-microglobulin-deficient class I-negative melanoma variants derived from patients undergoing specific T cell therapy are lysed by heterologous as well as autologous natural killer (NK) lines and clones, but not by specific T cells. Moreover, the minor NK cell fraction but not the major T cell fraction derived from heterologous lymphokine activated killer cells kills those tumor cell lines. ICAM-1 expression by the different class I protein deficient tumors was correlated with their sensitivity to lysis by NK cells. Adoptive autologous NK therapy may be an important supplement to consider in the design of new cancer immunotherapies.