Tuberculosis continues to cause considerable human morbidity and mortality across the world, particularly in people coinfected with HIV. The emergence of multidrug resistance makes the medical treatment of tuberculosis even more difficult. Thus, the development of a tuberculosis vaccine is a global health priority. Here we review the data concerning the role of CD8+ T cells in immunity to tuberculosis and consider how CD8+ T cells can be elicited by vaccination. Many immunization strategies have the potential to elicit CD8+ T cells, and we critically review the data supporting a role for vaccine-induced CD8+ T cells in protective immunity. The synergy between CD4+ and CD8+ T cells suggests that a vaccine which elicits both T cell subsets has the best chance at preventing tuberculosis.