Increasing attention has been devoted to elucidating the mechanism of lost or decreased expression of MHC or melanoma-associated antigens (MAAs), which may lead to tumor escape from immune recognition. Loss of expression of HLA class I or MAA has, as an undisputed consequence, loss of recognition by HLA class I-restricted cytotoxic T cells (CTLs). However, the relevance of down-regulation remains in question in terms of frequency of occurrence. Moreover the functional significance of epitope down-regulation, defining the relationship between MHC/epitope density and CTL interactions, is a matter of controversy, particularly with regard to whether the noted variability of expression of MHC/epitope occurs within a range likely to affect target recognition by CTLs. In this study, bulk metastatic melanoma cell lines originated from 25 HLA-A*0201 patients were analyzed for expression of HLA-A2 and MAAs. HLA-A2 expression was heterogeneous and correlated with lysis by CTLs. Sensitivity to lysis was also independently affected by the amount of ligand available for binding at concentrations of 0.001 to 1 mM. Natural expression of MAA was variable, independent from the expression of HLA-A*0201, and a significant co-factor determining recognition of melanoma targets. Thus, the naturally occurring variation in the expression of MAA and/or HLA documented by our in vitro results modulates recognition of melanoma targets and may (i) partially explain CTL-target interactions in vitro and (ii) elucidate potential mechanisms for progressive escape of tumor cells from immune recognition in vivo.