Recurrent solid malignancies are often refractory to standard therapies. Although adoptive T cell transfer may benefit select individuals, the majority of patients succumb to their disease. To address this important clinical dilemma, we developed a mouse melanoma model in which initial regression of advanced disease was followed by tumor recurrence. During recurrence, Foxp3(+) tumor-specific CD4(+) T cells became PD-1(+) and represented >60% of the tumor-specific CD4(+) T cells in the host. Concomitantly, tumor-specific CD4(+) T effector cells showed traits of chronic exhaustion, as evidenced by their high expression of the PD-1, TIM-3, 2B4, TIGIT, and LAG-3 inhibitory molecules. Although blockade of the PD-1/PD-L1 pathway with anti-PD-L1 Abs or depletion of tumor-specific regulatory T cells (Tregs) alone failed to reverse tumor recurrence, the combination of PD-L1 blockade with tumor-specific Treg depletion effectively mediated disease regression. Furthermore, blockade with a combination of anti-PD-L1 and anti-LAG-3 Abs overcame the requirement to deplete tumor-specific Tregs. In contrast, successful treatment of primary melanoma with adoptive cell therapy required only Treg depletion or Ab therapy, underscoring the differences in the characteristics of treatment between primary and relapsing cancer. These data highlight the need for preclinical development of combined immunotherapy approaches specifically targeting recurrent disease.