There has been recent interest in the depletion of regulatory T cells (Tregs) as part of a multi-faceted approach to the immunotherapy of melanoma patients. This is in part due recent findings that convincingly show that Tregs are an integral part of regulating and even suppressing an immune response to growing tumor cells. We therefore compared three methods of Treg depletion and/or elimination, utilizing low dose cyclophosphamide (CY), a specific antibody directed against the IL-2 receptor found on Tregs (PC61) and the use of denileukin diftitox (DD), which is a fusion protein designed to have a direct cytocidal action on cells which express the IL-2 receptor. We show that CY administration resulted in the highest reduction in Tregs among the three reagents. However, the reduction in Tregs with CY was also associated with the concomitant reduction of CD8(+) T cells and a lack of tumor antigen priming. Utilization of DD resulted in a >50% Treg cell reduction without parallel cytocidal effects upon other T cell subsets but did not enhance anti-tumor immunity against B16 melanoma. Lastly, the PC61 showed a moderate reduction of Tregs that lasted longer than the other reagents, without a reduction in the total number of CD8(+) T cells. Furthermore, PC61 treatment did not abrogate tumor antigen-specific immunity elicited by dendritic cells (DC). We therefore conclude that PC61 administration was the most effective method of reducing Tregs in a murine melanoma model in addition to providing evidence of a synergistic effect when combined with DC-based immunotherapy.