Melanoma-reactive HLA-A x 0201-restricted cytotoxic T lymphocyte (CTL) lines generated in vitro lyse autologous and HLA-matched allogeneic melanoma cells and recognize multiple shared peptide antigens from tyrosinase, MART-1, and Pme117/gp100. However, a subset of melanomas fail to be lysed by these T cells. In the present report, four different HLA-A x 0201+ melanoma cell lines not lysed by melanoma-reactive allogeneic CTL have been evaluated in detail. All four are deficient in expression of the melanocytic differentiation proteins (MDP) tyrosinase, Pme117/gp100, gp75/ trp-1, and MART-1/Melan-A. This concordant loss of multiple MDP explains their resistance to lysis by melanoma-reactive allogeneic CTL and confirms that a subset of melanomas may be resistant to tumor vaccines directed against multiple MDP-derived epitopes. All four melanoma lines expressed normal levels of HLAA x 0201, and all were susceptible to lysis by xenoreactive-peptide-dependent HLA-A x 0201-specific CTL clones, indicating that none had identifiable defects in antigen-processing pathways. Despite the lack of shared MDP-derived antigens, one of these MDP-negative melanomas, DM331, stimulated an effective autologous CTL response in vitro, which was restricted to autologous tumor reactivity. MHC-associated peptides isolated by immunoaffinity chromatography from HLA-A1 and HLA-A2 molecules of DM331 tumor cells included at least three peptide epitopes recognized by DM331 CTL and restricted by HLA-A1 or by HLA-A x 0201. Recognition of these CTL epitopes cannot be explained by defined, shared melanoma antigens; instead, unique or undefined antigens must be responsible for the autologous-cell-specific anti-melanoma response. These findings suggest that immunotherapy directed against shared melanoma antigens should be supplemented with immunotherapy directed against unique antigens or other undefined antigens, especially in patients whose tumors do not express MDP.