We have recently shown that effective cytokine gene therapy of solid tumors in HLA-A2 transgenic (HHD) mice lacking murine MHC class I molecule expression results in the generation of HLA-A2–restricted CD8+ T effector cells selectively recognizing tumor blood vessel-associated pericytes and/or vascular endothelial cells. Using an HHD model in which HLA-A2 neg tumor (MC38 colon carcinoma or B16 melanoma) cells are not recognized by the CD8+ T cell repertoire, we now show that vaccines on the basis of tumor-associated blood vessel Ags (TBVA) elicit protective Tc1-dependent immunity capable of mediating tumor regression or extending overall survival. Vaccine efficacy was not observed if (HLA-A2 neg) wild-type C57BL/6 mice were instead used as recipient animals. In the HHD model, effective vaccination resulted in profound infiltration of tumor lesions by CD8+(but not CD4+) T cells, in a coordinate reduction of CD31+ blood vessels in the tumor microenvironment, and in the “spreading” of CD8+ T cell responses to alternate TBVA that were not intrinsic to the vaccine. Protective Tc1-mediated immunity was durable and directly recognized pericytes and/or vascular endothelial cells flow-sorted from tumor tissue but not from tumor-uninvolved normal kidneys harvested from these same animals. Strikingly, the depletion of CD8+, but not CD4+, T cells at late time points after effective therapy frequently resulted in the recurrence of disease at the site of the regressed primary lesion. This suggests that the vaccine-induced anti-TBVA T cell repertoire can mediate the clinically preferred outcomes of either effectively eradicating tumors or policing a state of (occult) tumor dormancy.