Mycobacterium bovis BCG is a potent stimulator of the cellular immune response and has potential as a recombinant vaccine vector. Disclosed are BCG strains that generate greater MHC class I presentation of a transgenic protein, relative to the unmutated parental strain, and that improve a recipients CD8+ T cell response against the transgenic protein following vaccination. The mycobacterial constructs and their respective t/ansposon mutant BCG strains exhibit increased immunogenicity that is several times greater than responses generated by the parental strain and other existing modified rBCG strains. Furthermore, upon introducing the SIV gag gene into these novel strains, we observed that these strains primed for increased CD8+ T cell responses in a heterologous prime/boost regimen, comparable to levels generated by plasmid DNA vaccines. Creation of a second generation rBCG vector that may be utilized as a vaccine vector for immunizing against a variety of pathogens.