Regulatory T cells (Tregs) are major immunosuppressors in tumor-bearing hosts. Although Treg-depletion therapy has been shown to induce a complete cure in tumor-bearing mice, this treatment is not always successful. Using 3-methylcholanthrene-induced primary mouse tumors, we examined the distinct regulation of Treg-mediated immunosuppression between carcinomas and sarcomas. We showed that the number of Tregs was greatly increased in squamous cell carcinoma (SCC)-bearing mice compared with sarcoma-bearing mice. This appeared to be because SCC produced higher levels of active transforming growth factor (TGF)-beta, which is essential for inducing Tregs, compared with sarcoma. Moreover, SCC, but not sarcomas, were refractory to Treg-depletion therapy by treatment with anti-CD25 mAb. The refractoriness of SCC against Treg-depletion therapy was due to the rapid recovery of Tregs in SCC-bearing mice compared with sarcoma-bearing mice. However, combination treatment of anti-TGF-beta mAb with anti-CD25 mAb caused a significant reduction in Treg recovery and induced a complete cure in SCC-bearing mice. Thus, we showed the refractoriness of mouse carcinoma against Treg-depletion therapy using anti-CD25 mAb treatment. We also proposed a novel Treg-blocking combination therapy using anti-CD25 mAb and anti-TGF-beta mAb to induce a complete cure of tumor-bearing hosts.