The attenuated strain of Mycobacterium bovis known as bacille Calmette-Guérin (BCG) has been widely used as a vaccine for prevention of disease by Mycobacterium tuberculosis, but with relatively little evidence of success. Recent studies suggest that the failure of BCG may be due to its retention of immune evasion mechanisms that delay or prevent the priming of robust protective cell-mediated immunity. Here we describe an approach to enhance the immunogenicity of BCG by incorporating glycolipid activators of CD1d–restricted Natural Killer T cells (NKT cells), a conserved T cell subset with the potential to augment many types of immune responses. A method was developed for stably incorporating two forms of the NKT cell activator α-galactosylceramide (αGalCer) into live BCG organisms, and the impact of this on stimulation of T cell responses and protective anti-mycobacterial immunity was evaluated. We found that live BCG containing relatively small amounts of incorporated αGalCer retained the ability to robustly activate NKT cells. Compared to immunization with unmodified BCG, the glycolipid-modified BCG stimulated increased maturation of dendritic cells and markedly augmented the priming of antigen-specific CD8+ T cells responses. These effects were correlated with improved protective effects of vaccination in mice challenged with virulent M. tuberculosis. These results support the view that mycobacteria possess mechanisms to avoid stimulation of CD8+ T cell responses, and that such responses contribute significantly to protective immunity against these pathogens. Our findings raise the possibility of a simple modification of BCG that could yield a more effective vaccine for control of tuberculosis.