Provided herein is a multivalent Brucella vaccine expressing at least one heterologous M. tuberculosis antigen. The vaccines described herein serve as an environmentally safe bivalent vaccine for protection against Brucella and Mycobacterium infections simultaneously. In particular, a multivalent vaccine comprising a Brucella strain transformed with a vector that expresses at least one M. tuberculosis antigen, where the M. tuberculosis antigen(s) is codon optimized for the Brucella strain is provided. In some aspects, the Brucella strain is B. abortus strain RB51 leuB and the M. tuberculosis antigen is one or more of Ag85B, Rv2660c, and ESAT6.