Tuberculosis (TB) remains a global health burden for which safe vaccines are needed. BCG has limitations as a TB vaccine so we have focused on live attenuated Mycobacterium tuberculosis mutants as vaccine candidates. Prior to human studies, however, it is necessary to demonstrate safety in non-human primates (NHP). In this study, we evaluate the safety and efficacy of two live attenuated M. tuberculosis double deletion vaccine strains mc²6020 (ΔlysA ΔpanCD) and mc²6030 (ΔRD1 ΔpanCD) in cynomolgus macaques. In murine models, mc²6020 is rapidly cleared while mc²6030 persists. Both mc²6020 and mc²6030 were safe and well tolerated in cynomolgus macaques. Following a high-dose intrabronchial challenge with virulent M. tuberculosis, mc²6020-vaccinates were afforded a level of protection intermediate between that elicited by BCG vaccination and no vaccination. BCG vaccinates had reduced tuberculosis-associated pathology and improved clinical scores as compared to saline and mc²6030 vaccinates, but survival did not differ among the groups.