Despite the success of immune checkpoint blockade in melanoma, the majority of patients do not respond. We hypothesized that the T and NK cell subset frequencies and expression levels of their receptors may predict responses and clinical outcome of anti-CTLA-4 treatment. We thus characterized the NK and T cell phenotype, as well as serum levels of several cytokines in 67 melanoma patients recruited in Italy and Sweden, using samples drawn prior to and during treatment. Survival correlated with low expression of the inhibitory receptor TIM-3 on circulating T and NK cells prior to and during treatment and with the increased frequency of mature circulating NK cells (defined as CD3(-)CD56(dim) CD16(+)) during treatment. Survival also correlated with low levels of IL-15 in the serum. Functional experiments in vitro demonstrated that sustained exposure to IL-15 enhanced the expression of PD-1 and TIM-3 on both T and NK cells, indicating a causative link between high IL-15 levels and enhanced expression of TIM-3 on these cells. Receptor blockade of TIM-3 improved NK cell-mediated elimination of melanoma metastasis cell lines in vitro. These observations may lead to the development of novel biomarkers to predict patient response to checkpoint blockade treatment. They also suggest that induction of additional checkpoints is a possibility that needs to be considered when treating melanoma patients with IL-15.