Abstract Development of effective vaccination approaches to treat established tumors represents a focus of intensive research because such approaches offer the promise of enhancing immune system priming against tumor Ags via restimulation of pre-existing (memory) antitumoral helper and effector immune cells. However, inhibitory mechanisms, which function to limit the recall responses of tumor-specific immunity, remain poorly understood and interfere with therapies anticipated to induce protective immunity. The mouse renal cell carcinoma (RENCA) tumor model was used to investigate variables affecting vaccination outcomes. We demonstrate that although a whole cell irradiated tumor cell vaccine can trigger a functional antitumor memory response in the bone marrows of mice with established tumors, these responses do not culminate in the regression of established tumors. In addition, a CD103+ regulatory T (Treg) cell subset accumulates within the draining lymph nodes of tumor-bearing mice. We also show that B7-H1 (CD274, PD-L1), a negative costimulatory ligand, and CD4+ Treg cells collaborate to impair the recall responses of tumor-specific memory T cells. Specifically, mice bearing large established RENCA tumors were treated with tumor cell vaccination in combination with B7-H1 blockade and CD4+ T cell depletion (triple therapy treatment) and monitored for tumor growth and survival. Triple treatment therapy induced complete regression of large established RENCA tumors and raised long-lasting protective immunity. These results have implications for developing clinical antitumoral vaccination regimens in the setting in which tumors express elevated levels of B7-H1 in the presence of abundant Treg cells.