Environmental shedding of genetically manipulated microorganisms is an issue impeding the development of new live vaccines. We have investigated the immunogenicity of a number of novel Salmonella enterica serotype Typhimurium oral vaccine candidates that express the fragment C (TetC) component of tetanus toxin and harbor combinations of additional mutations in genes shdA, misL, and ratB that contribute to the persistence of serotype Typhimurium's colonization of the intestine. Serotype Typhimurium aroA (TetC) derivatives harboring additional mutations in either shdA or misL or combinations of these mutations exhibited a marked decrease in shedding of the vaccine strain in the feces of orally vaccinated mice. However, equivalent levels of anti-TetC and anti-Salmonella lipopolysaccharide immunoglobulin G (IgG), IgG1, IgG2a, and IgA were detected in sera of the vaccinated but not of the control mice. Cellular immune responses to TetC were detected in all vaccinated mice, regardless of the presence of the additional mutations in shdA or misL. Further, immunization with serotype Typhimurium aroA candidate vaccines harboring shdA and misL afforded complete protection against challenge with a virulent strain of serotype Typhimurium.