Tumors that progress do so via their ability to escape the antitumor immune response through several mechanisms, including developing ways to induce the differentiation and/or recruitment of CD4⁺CD25⁺ Tregs. The Tregs, in turn, inhibit the cytotoxic function of T cells and NK cells, but whether they have an effect on the cytotoxic function of tumor-infiltrating DCs (TIDCs) has not been determined. Here we have shown, in 2 rodent models of colon cancer, that CD4⁺CD25⁺ Tregs inhibit the ability of CD11b⁺ TIDCs to mediate TNF-related apoptosis-inducing ligand–induced (TRAIL-induced) tumor cell death. In both models of cancer, combination treatment with Mycobacterium bovis Bacillus Calmette-Guérin (BCG), which activates the innate immune system via TLR2, TLR4, and TLR9, and cyclophosphamide (CTX), which depletes Tregs, eradicated the tumors. Further analysis revealed that the treatment led to a marked increase in the number of CD11b⁺ TIDCs that killed the tumor cells via a TRAIL-dependent mechanism. Furthermore, acquisition of TRAIL expression by the CD11b⁺ TIDCs was induced by BCG and dependent on signaling through TLR2, TLR4, and TLR9. In vivo transfer of Tregs abrogated the ability of BCG to induce CD11b⁺ TIDCs to express TRAIL and thereby nullified the efficacy of the CTX-BCG treatment. Our data have therefore delineated what we believe to be a novel mechanism by which Tregs inhibit the antitumor immune response.