In previous studies we have shown that a pantothenate auxotroph of Myocbacterium bovis BCG (BCGΔpanCD) expressing HIV-1 subtype C Gag induced Gag-specific immune responses in mice and Chacma baboons after prime-boost immunization in combination with matched rMVA and VLP vaccines respectively. In this study recombinant BCG (rBCG) expressing HIV-1 subtype C reverse transcriptase and a truncated envelope were constructed using both the wild type BCG Pasteur strain as a vector and the pantothenate auxotroph. Mice were primed with rBCG expressing Gag and RT and boosted with a recombinant MVA, expressing a polyprotein of Gag, RT, Tat and Nef (SAAVI MVA-C). Priming with rBCGΔpanCD expressing Gag or RT rather than the wild type rBCG expressing Gag or RT resulted in higher frequencies of total HIV-specific CD8+ T cells and increased numbers of T cells specific to the subdominant Gag and RT epitopes. Increasing the dose of rBCG from 105 cfu to 107 cfu also led to an increase in the frequency of responses to subdominant HIV epitopes. A mix of the individual rBCGΔpanCD vaccines expressing either Gag, RT or the truncated Env primed the immune system for a boost with SAAVI MVA-C and generated five-fold higher numbers of HIV-specific IFN-γ-spot forming cells than mice primed with rBCGΔpanCD containing an empty vector control. Priming with the individual rBCGΔpanCD vaccines or the mix and boosting with SAAVI MVA-C also resulted in the generation of HIV-specific CD4+ and CD8+ T cells producing IFN-γ and TNF-α and CD4+ cells producing IL-2. The rBCG vaccines tested in this study were able to prime the immune system for a boost with rMVA expressing matching antigens, inducing robust, HIV-specific T cell responses to both dominant and subdominant epitopes in the individual proteins when used as individual vaccines or in a mix.