Expansion and recruitment of CD4(+) Foxp3(+) regulatory T (T reg) cells are mechanisms used by growing tumors to evade immune elimination. In addition to expansion of effector T cells, successful therapeutic interventions may require reduction of T reg cells within the tumor microenvironment. We report that the combined use of the alkylating agent cyclophosphamide (CTX) and an agonist antibody targeting the co-stimulatory receptor OX40 (OX86) provides potent antitumor immunity capable of regressing established, poorly immunogenic B16 melanoma tumors. CTX administration resulted in tumor antigen release, which after OX86 treatment significantly enhanced the antitumor T cell response. We demonstrated that T reg cells are an important cellular target of the combination therapy. Paradoxically, the combination therapy led to an expansion of T reg cells in the periphery. In the tumor, however, the combination therapy induced a profound T reg cell depletion that was accompanied by an influx of effector CD8(+) T cells leading to a favorable T effector/T reg cell ratio. Closer examination revealed that diminished intratumoral T reg cell levels resulted from hyperactivation and T reg cell-specific apoptosis. Thus, we propose that CTX and OX40 engagement represents a novel and rational chemoimmunotherapy.