Non-typhoidal includes thousands of serovars that are leading causes of foodborne diarrheal illness worldwide. In this study, we constructed three bivalent vaccines for preventing both Typhimurium and Newport infections by using the aspartate semialdehyde dehydrogenase (Asd)-based balanced-lethal vector-host system. The constructed Asd plasmid pCZ11 carrying a subset of the Newport O-antigen gene cluster including the genes was introduced into three Typhimurium mutants: SLT19 (Δ) with a smooth LPS phenotype, SLT20 (Δ Δ) with a rough LPS phenotype, and SLT22 (Δ Δ Δ P) with a smooth LPS phenotype when grown with arabinose. Immunoblotting demonstrated that SLT19 harboring pCZ11 [termed SLT19 (pCZ11)] co-expressed the homologous and heterologous O-antigens; SLT20 (pCZ11) exclusively expressed the heterologous O-antigen; and when arabinose was available, SLT22 (pCZ11) expressed both types of O-antigens, while in the absence of arabinose, SLT22 (pCZ11) expressed only the heterologous O-antigen. Exclusive expression of the heterologous O-antigen in Typhimurium decreased the swimming ability of the bacterium and its susceptibility to polymyxin B. Next, the gene was deleted from the three recombinant strains for attenuation purposes, generating the three bivalent vaccine strains SLT25 (pCZ11), SLT26 (pCZ11), and SLT27 (pCZ11), respectively. Groups of BALB/c mice (12 mice/group) were orally immunized with 10 CFU of each vaccine strain twice at an interval of 4 weeks. Compared with a mock immunization, immunization with all three vaccine strains induced significant serum IgG responses against both Typhimurium and Newport LPS. The bacterial loads in the mouse tissues were significantly lower in the three vaccine-strain-immunized groups than in the mock group after either Typhimurium or Newport lethal challenge. All of the mice in the three vaccine-immunized groups survived the lethal Typhimurium challenge. In contrast, SLT26 (pCZ11) and SLT27 (pCZ11) conferred full protection against lethal Newport challenge, but SLT25 (pCZ11) provided only 50% heterologous protection. Thus, we developed two novel bivalent vaccines, SLT26 (pCZ11) and SLT27 (pCZ11), suggesting that the delivery of a heterologous O-antigen in attenuated strains is a prospective approach for developing vaccines with broad serovar coverage.