The global epidemic of tuberculosis (TB), fueled by the growing HIV pandemic, warrants the development of a safe and effective vaccine against TB. We report the construction and characterization of an unlinked double deletion mutant of Mycobacterium tuberculosis H37Rv that deletes both the primary attenuating mutation of BCG (DeltaRD1) and two genes required for the synthesis of pantothenate (DeltapanCD). The M. tuberculosis DeltaRD1 DeltapanCD (mc(2)6030) mutant undergoes limited replication in mice, and yet is both significantly safer than BCG in immunocompromised mice and also safe in guinea pigs. Additionally, the mc(2)6030 strain does not reactivate in a mouse chemo-immunosuppression model. Importantly, long-lived protective immune responses following immunization with the mc(2)6030 strain prolong the survival of wild type mice, and CD4-deficient mice against an aerosol challenge with virulent M. tuberculosis. Given its overall safety and effectiveness, the mc(2)6030 live attenuated strain should be considered as a human vaccine candidate for protecting both healthy and HIV-infected individuals against TB.