The anti-tumor properties of Toll-like receptor (TLR) 9 agonist CpG oligodeoxynucleotides (ODN) are enhanced by combinations with several cytotoxic chemotherapy regimens. The mechanisms of this added benefit, however, remain unclear. We now report that, similar to the depletion of regulatory T cells (Treg) using anti-CD25, paclitaxel increased the anti-tumor effect of the TLR9 agonist PF-3512676 in a CD8(+) T cell-dependent fashion. Paclitaxel treatment decreased Treg numbers in a TLR4-independent fashion, and preferentially affected cycling Treg expressing high levels of FoxP3. The paclitaxel-induced reduction in Treg FoxP3 expression was associated with reduced inhibitory function. Adoptively transferred tumor-antigen specific CD8(+) T cells proliferated better in mice treated with paclitaxel and their recruitment in the tumor was increased. However, the systemic frequency of PF-3512676-induced tumor-antigen specific effector CD8(+) T cells decreased with paclitaxel, suggesting opposite effects of paclitaxel on the anti-tumor response. Finally, gene expression profiling and studies of tumor-associated immune cells revealed a complex modulation of the PF-3512676-induced immune response by paclitaxel, including a decrease of IL-10 expression and an increase in IL-17-secreting CD4(+) T cells. Collectively, these data suggest that paclitaxel combined with PF-3512676 may not only promote a better anti-tumor CD8(+) response though increased recruitment in the tumor, possibly through Treg depletion and suppression, but also exerts more complex immune modulatory effects.