Tumor associated macrophages (TAMs) are well known to play a very important role in tumor angiogenesis and metastasis. The suppression of TAMs in the tumor-microenvironment (TME) provides a novel strategy to inhibit tumor growth and dissemination by remodeling the tumor's stroma. Here, we tested our hypothesis that suppression of TAMs can be achieved in syngeneic BALB/c mice with oral minigene vaccines against murine MHC class I antigen epitopes of Legumain, an asparaginyl endopeptidase and a member of the C13 family of cystine proteases which is overexpressed on TAMs in the tumor stroma. Vaccine vectors were constructed and transformed into attenuated Salmonella typhimurium (Dam ( - ) , AroA ( - )) for oral delivery. Groups of mice received either the expression vectors encoding the Legumain H-2D or 2K epitopes or the control empty vector by gavage. The efficacy of the minigene vaccines was determined by their ability to protect mice from lethal tumor cell challenges, the induction of a specific CTL response as well as IFN-gamma release, and inhibition of tumor angiogenesis. We demonstrated that the Legumain minigene vaccine provided effective protection against tumor cell challenge by inducing a specific CD8+ T-cell response against Legumain+ TAMs in our breast tumor model. The protection, induced by this T-cell response, mediated by the Legumain Kd minigene, is also responsible for lysing D2F2 breast carcinoma cells in syngeneic BALB/c mice and for suppressing tumor angiogenesis. Importantly, in a prophylactic setting, the minigene vaccine proved to be of similar anti-tumor efficacy as a vaccine encoding the entire Legumain gene. Together, our findings establish proof of concept that a Legumain minigene vaccine provides a more flexible alternative to the whole gene vaccine, which may facilitate the future design and clinical applications of such a vaccine for cancer prevention.