Mycobacterium strains that have an enhanced ability to elicit a MHC-Class I-restricted CD8.sup.+ T cell immune response are provided. The Mycobacterium strains are genetically engineered to express: a endosomolytic protein that is active at neutral pH (e.g. Perfringolysin O), permitting escape of the Mycobacterium from endosomes into the cytoplasm of the cell; and antigens of interest, such as tuberculosis antigens. The invention also provides vaccine preparations containing such Mycobacterium strains.