Despite its potent immunostimulatory properties, vaccination with autologous tumor-derived gp96 has relatively modest antitumor effect in a range of clinical trials. Based on our previous study showing a gp96-mediated immune balance between CTL and Tregs, here we investigated possible synergy between gp96 vaccine and systemic Treg depletion on induction of antitumor T-cell immunity and the mechanisms accounting for synergistic efficacy. In gp96–peptide complex immunized BALB/c mice, anti-CD25 mAb treatment significantly increased IFN-γ-producing CD8⁺ and CD4⁺ T cells by about 1–2-fold in spleen and 40–50% in lymph node. A significantly higher number of peptide-specific CTL were observed under anti-CD25 mAb treatment compared with no treatment. Moreover, Treg depletion synergistically improved the anticancer activity of tumor-derived gp96 vaccine in the poorly immunogenic and highly tumorigenic B16 melanoma model in C57BL/6 J mice. While gp96 immunization alone led to the modest enhancement of CTL activities in spleen, the combination with Treg depletion dramatically increased tumor-specific CTL responses. In addition, the combination resulted in a significant increase of CD8⁺ T-cell infiltration in tumor, which correlated with an enhanced inhibition of tumor growth. Our results provide evidence that targeting Tregs may provide a more efficient strategy to potentiate gp96-mediated T-cell responses and enhance the antitumor efficiency of gp96-based therapeutic vaccine.