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. Int. J. Cancer: 80, 781–790 (1999). © 1999 Wiley‐Liss, Inc.