Auxotrophic mutants of Mycobacterium tuberculosis have been proposed as new vaccine candidates. We have analyzed the virulence and vaccine potential of M. tuberculosis strains containing defined mutations in genes involved in methionine (metB), proline (proC), or tryptophan (trpD) amino acid biosynthesis. The metB mutant was a prototrophic strain, whereas the proC and trpD mutants were auxotrophic for proline and tryptophan, respectively. Following infection of murine bone marrow-derived macrophages, H37Rv and the metB mutant strain survived intracellularly for over 10 days, whereas over 90% of proC and trpD mutants were killed during this time. In SCID mice, both H37Rv and the metB mutant were highly virulent, with mouse median survival times (MST) of 28.5 and 42 days, respectively. The proC mutant was significantly attenuated (MST, 130 days), whereas the trpD mutant was essentially avirulent in an immunocompromised host. Following infection of immunocompetent DBA mice with H37Rv, mice survived for a median of 83.5 days and the metB mutant now showed a clear reduction in virulence, with two of five infected mice surviving for 360 days. Both proC and trpD mutants were avirulent (MST of >360 days). In vaccination studies, prior infection with either the proC or trpD mutant gave protection equivalent (proC mutant) to or better (trpD mutant) than BCG against challenge with M. tuberculosis H37Rv. In summary, proC and trpD genes are essential for the virulence of M. tuberculosis, and mutants with disruptions in either of these genes show strong potential as vaccine candidates.