During the past few years, a number of studies reported that different melanoma cell lines could be extensively lysed in vitro by IL-2-activated NK cells at appropriate effector/target ratios. Here, we show, by histological evaluation of different melanoma lesions, that NK/target-cell ratios compatible with those allowing efficient melanoma cell killing in vitro are hardly reached at the tumor site. We then investigated the outcome of cocultures established at low NK/melanoma cell ratios. After initial NK-mediated lysis, residual melanoma cells acquired resistance to IL-2-activated NK cells. This reflected primarily an increased expression, on melanoma cells, of classical and nonclassical HLA class I molecules, accompanied by a partial downregulation of NKG2D-ligands, and was dependent on NK-mediated IFN-γ release. Consistently, melanoma lesions showed a higher HLA class I expression on tumor cells that were proximal to infiltrating NK cells. In long-term cocultures, the "protective phenotype" acquired by melanoma cells was lost over time. However, this phenomenon was counteracted by downregulation of relevant activating receptors in cocultured NK cells. Analysis of different NK-cell-activating cytokines indicated that IL-15 can partially overcome this novel tumor escape mechanism suggesting that IL-15, rather than IL-2, may be eligible for NK-cell-based immunotherapy.