Studies with Mycobacterium avium subsp. paratuberculosis (Map) in cattle revealed deletion of relA, a global regulator gene, abrogated ability of the mutant to establish a persistent infection, attributed to development of an immune response that cleared infection. Analysis of the recall response demonstrated presence of CD8 cytotoxic T cells that kill intracellular bacteria. Replication of the primary response demonstrated the CTL response could be elicited with the ΔMap/relA mutant or the target of the immune response, a 35 kD membrane protein. Follow up comparative studies with Mycobacterium bovis bacillus Calmette-Guérin (BCG) and a BCG relA (ΔBCG/relA) deletion mutant revealed deletion of relA enhanced the CTL response compared to BCG. Analysis of the cytokine profile of cells proliferating in response to stimulation with BCG or BCG/relA showed increased expression of IFN-γ, TNF-α, and IL-17 by cells stimulated with ΔBCG/relA in comparison with BCG. The proliferative and CTL responses were markedly reduced in response to stimulation with heat killed BCG or ΔBCG/relA. Intracellular bacterial killing was mediated through the perforin, granzyme B (GnzB), and the granulysin pathway. The data indicate relA is the Achilles’ heel for pathogenic mycobacteria and deletion may be key to improving efficacy of attenuated vaccines for mycobacterial pathogens.