Mycobacterium bovis BCG is an attractive vaccine vector against breast milk HIV transmission because it elicits Th1-type responses in newborns. However, BCG causes disease in HIV-infected infants. Genetically attenuated Mycobacterium tuberculosis (Mtb) mutants represent a safer alternative for immunocompromised populations. In the current study, we compared the immunogenicity in mice of three different recombinant attenuated Mtb strains expressing an HIV envelope (Env) antigen construct. Two of these strains (DeltalysA DeltapanCD Mtb and DeltaRD1 DeltapanCD Mtb) failed to induce significant levels of HIV Env-specific CD8(+) T cell responses. In striking contrast, an HIV-1 Env-expressing attenuated DeltalysA Mtb containing a deletion in secA2, which encodes a virulence-related secretion system involved in evading adaptive immunity, generated consistently measurable Env-specific CD8(+) T cell responses that were significantly greater than those observed after immunization with BCG expressing HIV Env. Similarly, another strain of DeltalysA DeltasecA2 Mtb expressing SIV Gag induced Gag- and Mtb-specific CD8(+) T cells producing perforin or IFNgamma, and Gag-specific CD4(+) T cells producing IFNgamma within 3 weeks after immunization in adult mice; in addition, IFNgamma-producing Gag-specific CD8(+) T cells and Mtb-specific CD4(+) T cells were observed in neonatal mice within 1 week of immunization. We conclude that DeltalysA DeltasecA2 Mtb is a promising vaccine platform to construct a safe combination HIV-TB vaccine for use in neonates.