We reported previously that vaccination of reconstituted, lymphopenic mice resulted in a higher frequency of tumor-specific effector T cells with therapeutic activity than vaccination of normal mice. Here, we show that lymphopenic mice reconstituted with spleen cells from tumor-bearing mice (TBM), a situation that resembles the clinical condition, failed to generate tumor-specific T cells with therapeutic efficacy. However, depletion of CD25(+) Treg from the spleen cells of TBM restored tumor-specific priming and therapeutic efficacy. Adding back TBM CD25(+) Treg to CD25(-) naïve and TBM donor T cells prior to reconstitution confirmed their suppressive role. CD25(+) Treg from TBM prevented priming of tumor-specific T cells since subsequent depletion of CD4(+) T cells did not restore therapeutic efficacy. This effect may not be antigen-specific as three histologically distinct tumors generated CD25(+) Treg that could suppress the T-cell immune response to a melanoma vaccine. Importantly, since ex vivo depletion of CD25(+) Treg from TBM spleen cells prior to reconstitution and vaccination fully restored the generation of therapeutic effector T cells, even in animals with established tumor burden, we have initiated a translational clinical trial of this strategy in patients with metastatic melanoma.