Cancer is one of the leading causes of death in the industrialized world and represents a tremendous social and economic burden. As conventional therapies fail to provide a sustainable cure for most cancer patients, the emerging unique immune therapeutic approach of bacteria-mediated tumor therapy (BMTT) is marching towards a feasible solution. Although promising results have been obtained with BMTT using various preclinical tumor models, for advancement a major concern is immunity against the bacterial vector itself. Pre-exposure to the therapeutic agent under field conditions is a reasonable expectation and may limit the therapeutic efficacy of BMTT. In the present study, we investigated the therapeutic potential of Salmonella and E. coli vector strains in naïve and immunized tumor bearing mice. Pre-exposure to the therapeutic agent caused a significant aberrant phenotype of the microenvironment of colonized tumors and limited the in vivo efficacy of established BMTT vector strains Salmonella SL7207 and E. coli Symbioflor-2. Using targeted genetic engineering, we generated the optimized auxotrophic Salmonella vector strain SF200 ( ΔlpxR9 ΔpagL7 ΔpagP8 ΔaroA ΔydiV ΔfliF) harboring modifications in Lipid A and flagella synthesis. This combination of mutations resulted in an increased immune-stimulatory capacity and as such the strain was able to overcome the efficacy-limiting effects of pre-exposure. Thus, we conclude that any limitations of BMTT concerning anti-bacterial immunity may be countered by strategies that optimize the immune-stimulatory capacity of the attenuated vector strains.