Bone marrow-derived dendritic cells engineered using recombinant adenovirus to secrete high levels of IL-12p70 dramatically inhibited the growth of established CMS4 sarcomas in BALB/c mice after intratumoral administration. An analysis of splenic CD8(+) T cells in regressor mice revealed a strong, complex reactivity pattern against high-performance liquid chromatography (HPLC)-resolved peptides isolated by acid elution from single-cell suspensions of surgically resected CMS4 lesions. Mass spectrometry analyses defined two major overlapping peptide species that derive from the murine hemoglobin-beta (HBB) protein within the most stimulatory HPLC fractions. Although cultured CMS4 tumor cells failed to express HBB mRNA based on reverse transcription-PCR analyses, prophylactic vaccination of BALB/c mice with vaccines containing HBB peptides promoted specific CD8(+) T-cell responses that protected mice against a subsequent challenge with CMS4 or unrelated syngeneic (HBB(neg)) tumors of divergent histology (sarcoma, carcinomas of the breast or colon). In situ imaging suggested that vaccines limit or destabilize tumor-associated vascular structures, potentially by promoting immunity against HBB+ vascular pericytes. Importantly, there were no untoward effects of vaccination with the HBB peptide on peripheral RBC numbers, RBC hemoglobin content, or vascular structures in the brain or eye.