In recent years, studies on the molecular and cellular mechanisms of immune responses against melanoma have contributed to a better understanding of how these tumours can be recognised by cytotoxic cells and the mechanisms they have developed to escape from innate and adaptive immunity. Lysis of melanoma cells by natural killer (NK) cells and cytolytic T cells is the result of a fine balance between signals transmitted by activating and inhibitory receptors. In addition to the T cell receptor, these were initially described as NK cell-associated receptors (NKRs) and were later also found on subsets of T lymphocytes, particularly effector-memory and terminally differentiated CD8 T cells. An increase of NKR(+)CD8(+) T cells has been found in melanoma patients, correlating with the expansion of differentiated effector CD8(+)CD28(null) CD27(null) T cells. NKRs can regulate the lysis of target cells expressing appropriate ligands. Activating receptors recognise ligands on tumours whereas inhibitory receptors are specific for MHC class I antigens and sense missing self. Altered expression of MHC class I antigens is frequently found on melanoma cells, preventing recognition by specific cytolytic T cells but favouring NK cell recognition. Changes in the expression of NKR-ligands in melanoma contribute in explaining the differences in the capacity of cytotoxic immune cells to control melanoma growth and dissemination.