Recombinant strains of Mycobacterium bovis bacille Calmette-Guerin (M. bovis BCG) comprising a heterologous nucleic acid sequence of Mycobacterium marinum (M. marinum) are provided. In some embodiments the heterologous nucleic acid sequence of M. marinum comprises a plurality of open reading frames, wherein the plurality of open reading frames comprise open reading frames that encode proteins each at least 95% homologous to the Mycobacterium marinum (M. marinum) proteins MMAR5445, MMAR5446, MMAR5447, MMAR5448, MMAR5449, MMAR5450, MMAR5451, MMAR5452, MMAR5453, and MMAR5455. In some embodiments the plurality of open reading frames further comprise an open reading frame that encodes a protein at least 95% homologous to the M. marinum proteins MMAR5443, MMAR5444, and MMAR5457. In some embodiments the plurality of open reading frames further comprise open reading frames that encode proteins at least 95% homologous to the M. marinum proteins MMAR5429, MMAR5430, MMAR5431, MMAR5432, MMAR5433, MMAR5434, MMAR5435, MMAR5436, MMAR5437, MMAR5438, MMAR5439, MMAR5440, MMAR5441, MMAR5442, MMAR5454, MMAR5456, MMAR5458, MMAR5459, MMAR5460, and MMAR5461. Pharmaceutical compositions, kits, methods of inducing an immune response against M. tuberculosis in a subject, and methods of treating an M. tuberculosis infection in a subject are also provided, among other things.