Three-quarters of a century after the introduction of Mycobacterium bovis BCG, the first tuberculosis vaccine, new vaccines for tuberculosis are finally entering clinical trials. This breakthrough is based not only on advances in proteomics and genomics which have made the construction of new vaccines possible, but also on a greatly expanded knowledge of the immunology of tuberculosis. Here we review our current understanding of how Mycobacterium tuberculosis subverts or survives the host's immune response to cause disease and why the current vaccination strategy, which relies on BCG, is only partially successful in countering the pathogen. This provides a background for describing the new generation of vaccines designed to supplement or replace the current vaccine and the different approaches they take to stimulate immunity against M. tuberculosis.