A third of the world's population is infected with Mycobacterium tuberculosis, and 2 million people die from tuberculosis every year even though the bacille Calmette Guérin (BCG) vaccine has been available for more than 75 years. In order to reduce the immense burden of tuberculosis, new vaccines or vaccination strategies, or both, are urgently needed. Why BCG vaccination has not reduced disease prevalence, especially in the developing world, is not yet understood. Important contributing factors might include background immunity induced by non-tuberculous environmental mycobacteria, diversity of BCG strains, and overattenuation of presently used strains. This review provides a summary of the immune responses thought to be important for protective tuberculosis immunity; various mycobacterial antigens that seem to be promising targets for vaccine-induced immunity; different vaccination approaches being developed for use in people; and the key issues involved in the selection of new vaccines for expanded phase II or III testing.