Tumor growth is an angiogenesis-dependent process and accompanied by the formation of hypoxic areas. Tumstatin is a tumor-specific angiogenesis inhibitor that suppresses the proliferation and induces the apoptosis of tumorous vascular endothelial cells. VNP20009, an attenuated Salmonella typhimurium strain, preferentially accumulates in the hypoxic areas of solid tumors. In this study, a novel Salmonella-mediated targeted expression system of tumstatin (VNP-Tum5) was developed under the control of the hypoxia-induced J23100 promoter to obtain anti-tumor efficacy in mice. Treatment with VNP-Tum5 effectively suppressed tumor growth and prolonged survival in the mouse model of B16F10 melanoma. VNP-Tum5 exhibited a higher efficacy in inhibiting the proliferation and inducing the necrosis and apoptosis of B16F10 cells in vitro and in vivo compared with VNP (control). VNP-Tum5 significantly inhibited the proliferation and migration of mouse umbilical vascular endothelial cells to impede angiogenesis. VNP-Tum5 downregulated the expression of anti-vascular endothelial growth factor A, platelet endothelial cell adhesion molecule-1, phosphorylated phosphoinositide 3 kinase, and phosphorylated protein kinase B and upregulated the expression of cleaved-caspase 3 in tumor tissues. This study is the first to use tumstatin-transformed VNP20009 as a tumor-targeted system for treatment of melanoma by combining anti-tumor and anti-angiogenic effects.