Recombinant Mycobacterium bovis bacillus Calmette-Guèrin (rBCG) has been explored as a vector for vaccines against HIV because of its ability to induce long lasting humoral and cell mediated immune responses. To maximize the potential for rBCG vaccines to induce effective immunity against HIV, various strategies are being employed to improve its ability to prime CD8+ T cells, which play an important role in the control of HIV infections. In this study we adopted a previously described approach of incorporating glycolipids that activate CD1d-restricted natural killer T (NKT) cells to enhance priming of CD8+ T cells by rBCG strains expressing an SIV Gag antigen (rBCG-SIV gag). We found that the incorporation of the synthetic NKT activating glycolipid α-galactosylceramide (α-GC) into rBCG-SIV gag significantly enhanced CD8+ T cell responses against an immunodominant Gag epitope, compared to responses primed by unmodified rBCG-SIV gag. The abilities of structural analogues of α-GC to enhance CD8+ T cell responses to rBCG were compared in both wild type and partially humanized mice that express human CD1d molecules in place of mouse CD1d. These studies identified an α-GC analogue known as 7DW8-5, which has previously been used successfully as an adjuvant in non-human primates, as a promising compound for enhancing immunogenicity of antigens delivered by rBCG.vectors. Our findings support the incorporation of synthetic glycolipid activators of NKT cells as a novel approach to enhance the immunogenicity of rBCG-vectored antigens for induction of CD8+ T cell responses. The glycolipid adjuvant 7DW8-5 may be a promising candidate for advancing to non-human primate and human clinical studies for the development of HIV vaccines based on rBCG vectors.