Control of Johne's disease, caused by Mycobacterium avium subsp. paratuberculosis, has been difficult because of a lack of an effective vaccine. To address this problem we used targeted gene disruption to develop candidate mutants with impaired capacity to survive ex vivo and in vivo to test as a vaccine. We selected relA and pknG, genes known to be important virulence factors in Mycobacterium tuberculosis and Mycobacterium bovis, for initial studies. Deletion mutants were made in a wild type Map (K10) and its recombinant strain expressing the green fluorescent protein (K10-GFP). Comparison of survival in an ex vivo assay revealed deletion of either gene attenuated survival in monocyte-derived macrophages compared to survival of wild-type K10. In contrast, study in calves revealed survival in vivo was mainly affected by deletion of relA. Bacteria were detected in tissues from wild-type and the pknG mutant infected calves by bacterial culture and PCR at three months post infection. No bacteria were detected in tissues from calves infected with the relA mutant (P<0.05). Flow cytometric analysis of the immune response to the wild-type K10-GFP and the mutant strains showed deletion of either gene did not affect their capacity to elicit a strong proliferative response to soluble antigen extract or live Map. Quantitative RT-PCR revealed genes encoding IFN-γ, IL-17, IL-22, T-bet, RORC, and granulysin were up-regulated in PBMC stimulated with live Map three months post infection compared to the response of PBMC pre-infection. A challenge study in kid goats showed deletion of pknG did not interfere with establishment of an infection. As in calves, deletion of relA attenuated survival in vivo. The mutant also elicited an immune response that limited colonization by challenge wild type Map. The findings show the relA mutant is a good candidate for development of a live attenuated vaccine for Johne's disease.