Immune checkpoint inhibitors that maintain anti-tumor T cell response are used for treating patients with metastatic melanoma. Since the response to treatment is extremely variable, biomarkers are urgently needed to identify patients who could benefit from such therapy. We combined single-cell RNA-sequencing and multiparameter flow cytometry to determine changes in circulating CD8+ T cells in patients with metastatic melanoma. A total of 28 patients starting anti-PD1 therapy were enrolled and followed for 6 months: 17 responded to therapy, whilst 11 did not. The proportion of activated and proliferating CD8+ T cells and of mucosal associated invariant T (MAIT) cells was significantly higher in responders before starting therapy and was maintained over time. MAIT cells expressed higher level of CXCR4 and produced more granzyme B; in silico analysis revealed that they are present in the tumor microenvironment. Finally, patients with higher levels of MAIT showed a better response to treatment.