An estimated 2 billion people are latently infected with Mycobacterium tuberculosis, the majority of which are already BCG vaccinated and repeatedly sensitized to mycobacterial strains from the environment. To be successful in the high endemic regions, any future TB vaccine strategy will have to be tailored in accordance with the resulting complexity of the TB infection and anti-mycobacterial immune response. In this review we will discuss some of the most advanced attempts to address this challenge.