Melanomas are aggressive skin tumors characterized by high metastatic potential. Immunotherapy is a valuable alternative for metastatic melanoma patients resistant to chemotherapy. Natural Killer (NK) cells are efficient anti-tumor cytotoxic effectors. We previously showed that blood NK cells from stage IV metastatic melanoma patients display decreased NK receptors and that chemotherapy modifies the functional status of blood NK cells. To investigate the role of NK cells along melanoma progression, we have here studied NK cells from patients at different stages of the disease. First, we showed that ex vivo NK cells from certain stage III–IV patients displayed low degranulation potential. Using a dynamic label-free assay, we found that immunoselected IL-2 activated blood NK cells from patients efficiently lysed melanoma cells through NKp46 and NKG2D receptors, independently to the clinical stage. Moreover, the ex vivo phenotype of circulating NK cells from 33 patients (stage I to IV) was extensively analyzed. NK cells from patients displayed higher variability in the percentages of Natural Cytotoxicity Receptors (NCR) and Natural Killer Group 2D (NKG2D) receptor expression compared to donor NK cells. The main defect was the decreased expression of NCR1 (NKp46) by NK cells from metastatic patients. Interestingly, we found a positive correlation between the NK cell percentages of NKp46 and the duration of stage IV in melanoma patients. Finally, we showed that NK cells infiltrated primary melanomas and displayed a predominant peritumoral distribution. These results are new arguments for the development of NK-based therapies in melanoma patients.