Purpose: PD-1 blockade induces durable responses in patients with metastatic melanoma and prolongs relapse-free survival in patients with resected melanoma; however, current biomarkers do not consistently associate with patient responses. In this study, we investigated the impact of nivolumab therapy on peripheral blood regulatory T cells (Treg) and its relation to patient outcomes. Experimental Design: Peripheral blood Tregs and conventional CD4 þ T cells from patients with resected high-risk melanoma treated with adjuvant nivolumab were assessed for gene expression changes by RNA-seq. Percentages of circulating Tregs and phosphorylated-STAT3 (pSTAT3) expression levels were assessed by flow cytometry and validated in an independent cohort of active disease patients. Suppressive function of Tregs was assessed in allogeneic mixed lymphocyte reactions. Results: Tregs from non-relapse patients had increased expression of proliferation associated genes. An increase in the proportion of circulating Tregs and pSTAT3 expression and a reduction in Treg-suppressive capacity were observed in non-relapsing, but not relapsing patient samples 13 weeks after starting treatment. In vitro blockade of PD-1 increased Treg percentages and pSTAT3 expression, and reduced Treg-suppressive function. PD-1 blockade also led to IL10 production by T cells, resulting in higher Treg proliferation. The addition of a STAT3 inhibitor ameliorated the increase in Tregs, enhanced suppressive function, and decreased T-cell IL10 production in vitro. Conclusions: These results demonstrate that induction of pSTAT3, reduced suppressive function, and a paradoxical increase in Treg proliferation are novel correlates of patient benefit from PD-1 blockade.