Transduction of B16 melanoma cells with IFNα (B16-IFNα) enhances CD8⁺ T-cell-dependent tumor immunity in mice, resulting in delayed outgrowth in vivo. Here we provide evidence that CD4⁺ T cells down-regulate the IFNα-induced tumor immune defense. Importantly, depletion of regulatory CD25⁺ CD4⁺ T cells prevented growth of B16-IFNα in most mice and promoted long-lasting protective tumor immunity. Rejection of B16-IFNα could also be achieved with therapeutic injections of dendritic cells genetically engineered to express the melanoma antigen tyrosinase-related protein 2. These results support the development of novel strategies for the immunotherapy of melanoma using IFNα in combination with elimination of regulatory T cells or antigen-specific immunization.