Background Nivolumab is an anti-PD1 antibody that has dramatically improved metastatic melanoma patients’ outcomes. Nevertheless, many patients are resistant to PD-1 inhibition, occasionally experiencing severe off-target immune toxicity. In addition, no robust and reproducible biomarkers have yet been validated to identify the correct selection of patients who will benefit from anti-PD-1 treatment avoiding unwanted side effects. However, the strength of CD26 expression on CD4+ T lymphocytes permits the characterization of three subtypes with variable degrees of responsiveness to tumors, suggesting that the presence of CD26-expressing T cells in patients might be a marker of responsiveness to PD-1-based therapies. Methods The frequency distribution of peripheral blood CD26-expressing cells was investigated employing multi-parametric flow cytometry in 69 metastatic melanoma patients along with clinical characteristics and blood count parameters at baseline (W0) and compared to 20 age- and sex-matched healthy controls. Percentages of baseline CD4+CD26high T cells were correlated with the outcome after nivolumab treatment. In addition, the frequency of CD4+CD26high T cells at W0 was compared with those obtained after 12 weeks (W1) of therapy in a sub-cohort of 33 patients. Results Circulating CD4+CD26high T cells were significantly reduced in melanoma patients compared to healthy subjects (p<0.001). In addition, a significant association was observed between a low baseline percentage of CD4+CD26high T cells (<7.3%) and clinical outcomes, measured as overall survival (p=0.010) and progression-free survival (p=0.014). Moreover, patients with clinical benefit from nivolumab therapy had significantly higher frequencies of circulating CD4+CD26high T cells than patients with non-clinical benefit (p=0.004) at 12 months. Also, a higher pre-treatment proportion of circulating CD4+CD26high T cells was correlated with Disease Control Rate (p=0.014) and best Overall Response Rate (p=0.009) at 12 months. Interestingly, after 12 weeks (W1) of nivolumab treatment, percentages of CD4+CD26 high T cells were significantly higher in comparison with the frequencies measured at W0 (p < 0.0001), aligning the cell counts with the ranges seen in the blood of healthy subjects. Conclusions Our study firstly demonstrates that peripheral blood circulating CD4+CD26high T lymphocytes represent potential biomarkers whose perturbations are associated with reduced survival and worse clinical outcomes in melanoma patients.