A safe and effective HIV vaccine is required to significantly reduce the number of people becoming infected with HIV each year. In this study wild type Mycobacterium bovis BCG Pasteur and an attenuated pantothenate auxotroph strain (BCGΔpanCD) that is safe in SCID mice, have been compared as vaccine vectors for HIV-1 subtype C Gag. Genetically stable vaccines BCG[pHS400] (BCG-Gag) and BCGΔpanCD[pHS400] (BCGpan-Gag) were generated using the Pasteur strain of BCG, and a panothenate auxotroph of Pasteur respectively. Stability was achieved by the use of a codon optimised gag gene and deletion of the hsp60-lysA promoter-gene cassette from the episomal vector pCB119. In this vector expression of gag is driven by the mtrA promoter and the Gag protein is fused to the Mycobacterium tuberculosis 19 kDa signal sequence. Both BCG-Gag and BCGpan-Gag primed the immune system of BALB/c mice for a boost with a recombinant modified vaccinia virus Ankara expressing Gag (MVA-Gag). After the boost high frequencies of predominantly Gag-specific CD8(+) T cells were detected when BCGpan-Gag was the prime in contrast to induction of predominantly Gag-specific CD4(+) T cells when priming with BCG-Gag. The differing Gag-specific T-cell phenotype elicited by the prime-boost regimens may be related to the reduced inflammation observed with the pantothenate auxotroph strain compared to the parent strain. These features make BCGpan-Gag a more desirable HIV vaccine candidate than BCG-Gag. Although no Gag-specific cells could be detected after vaccination of BALB/c mice with either recombinant BCG vaccine alone, BCGpan-Gag protected mice against a surrogate vaccinia virus challenge.