Among the relatively large number of known tumor-associated antigens (TAA) which are recognized by human CD8 T-cells, Melan-A/MART-1 is one of the most—if not the most—frequently used target for anti-cancer vaccines in HLA-A2 + melanoma patients. In this study, we analyzed the killing of a large panel of melanoma cells by a high avidity, MART-1-specific T-cell clone or a MART-1-specific, polyclonal T-cell culture. Strikingly, we observed that the MART-1-specific T-cells only killed around half of the analyzed melanoma cell lines. In contrast a Bcl-2-specific T-cell clone killed all melanoma cell lines, although the T-cell avidity of this clone was significantly lower. The MART-1-specific T-cell clone expressed NKG-2D and was fully capable of releasing both perforin and Granzyme B. Notably, the resistance to killing by the MART-1-specific T-cells could be overcome by pulsing of the melanoma cells with the MART-1 epitope. Thus, the very frequently used MART-1 epitope was not expressed on the surface of many melanoma cell lines. Our data emphasize that the selected tumor antigens and/or epitopes are critical for the outcome of anti-cancer immunotherapy.