Four novel oral DNA vaccines provide protection against melanoma, colon, breast, and lung carcinoma in mouse models. Vaccines are delivered by attenuated Salmonella typhimurium to secondary lymphoid organs and respectively target vascular endothelial growth factor receptor-2, transcription factor Fos-related antigen-1, anti-apoptosis protein survivin and Legumain, an asparaginyl endopeptidase specifically overexpressed on tumor-associated macrophages (TAMs) in the tumor microenvironment (TME). These vaccines are all capable of inducing potent cell-mediated protective immunity against self-antigens, resulting in marked suppression of tumor growth and dissemination. Key mechanisms induced by these DNA vaccines include efficient suppression of angiogenesis in the tumor vasculature and marked activation of cytotoxic T cells, natural killer cells, and antigen-presenting dendritic cells. The vaccine targeting Legumain establishes the new paradigm whereby a reduction in the density of TAMs in the TME decreases the release of factors potentiating tumor growth and angiogenesis. This, in turn, remodels the TME and decreases its immunosuppressive milieu and thereby potentiates the DNA vaccine's ability to effectively suppress tumor cell proliferation, vascularization, and metastasis. It is anticipated that such research efforts will lead to novel DNA-based vaccines that will be effective for the treatment of cancer.