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. In this study, we describe an approach to enhance the immunogenicity of BCG by incorporating glycolipid activators of CD1d-restricted 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 into live BCG organisms, and the impact of this on stimulation of T cell responses and protective antimycobacterial immunity was evaluated. We found that live BCG containing relatively small amounts of incorporated α-galactosylceramide retained the ability to robustly activate NKT cells. Compared with immunization with unmodified BCG, the glycolipid-modified BCG stimulated increased maturation of dendritic cells and markedly augmented the priming of Ag-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.