The roles of NK cells in human melanoma remain only partially understood. We characterized NK cells from peripheral blood ex vivo by flow cytometry obtained from late stage (III/IV) melanoma patients. Interestingly, we found that the abundance of CD56^bright NK cells negatively correlate with overall patient survival, together with distant metastases, in a multivariate cox regression analysis. The patients’ CD56^bright NK cells showed upregulation of CD11a, CD38 and CD95 as compared to healthy controls, pointing to an activated phenotype as well as a possible immune regulatory role in melanoma patients. After stimulation in vitro, CD56^bright NK cells produced less TNFα and GMCSF in patients than controls. Furthermore, IFNγ production by the CD56^bright NK cells correlated inversely with overall survival. Our results highlight that abundance and function of CD56^bright NK cells are associated with melanoma patient survival, emphasizing the potential of NK cell subsets for biomarker discovery and future therapeutic targeting.