Background: Recent success of immunotherapies targeting the exhaustion markers CTLA-4 and PD-1 has inforced the role of CD8⁺T cell exhaustion in advanced melanoma patients. T cell exhaustion, has been extensively studied, however little is known about NK cell exhaustion in the same context. In this project, we defined NK cells phenotype in different stages of melanoma to examine its role in melanoma progression. Methods: NK cells were purified from the peripheral blood of a prospectively-enrolled cohort of 100 melanoma patients: stage I (n=56), stage II (n=21) and stages III/IV (n=23); in addition to 25 healthy donors. NK cells were characterized for the expression of activating (NKG2D and NKp46) and inhibitory receptors (Tim-3, KIRB1 and KIRNKAT2), function (cytotoxicity, IFN-γ production and proliferation) and the intracellular expression of the transcription factors (T-bet and Eomes). We then tested the association between NK cell phenotype and clinicopathological variables associated with melanoma prognosis. Unpaired T test was used to compare two groups, and ANOVA to compare more than two groups. Results: NK cells gradually develop a phenotypic and functional profile consistent with progressive exhaustion, from stage I to stage IV characterized by: 1) up-regulation of inhibitory receptors (Tim-3, KIRB1 and KIRNKAT2); 2) down-regulation of activating receptors (NKG2D and NKp46) and transcription factors (T-bet and Eomes); 3) loss of IFN-γ production,proliferation and cytotoxicity. Interestingly, the expression of Tim-3 and KIRB1 is higher, while the cytotoxic ability is reduced in patients with melanomas thicker than 1mm (Tim-3 – p=0.007; KIRB1 – p=0.03; cytotoxicity – p=0.05). Higher Tim-3 expression is associated with ulceration (p=0.009) and with mitosis (p=0.001). Moreover, higher expression of Tim-3 and KIRB1, and a lower cytotoxic ability is associated with local or distant metastases (Tim-3 – P=0.002; KIRB1 – p=0.0009; cytotoxicity – p=0.0005). Conclusions: Data demonstrate that NK cells become progressively exhausted in the context of melanoma progression. NK cells start acquiring this phenotype in early stages which suggests that targeting them earlier can be be a novel therapeutic strategy.