Mycobacterium bovis bacillus Calmette-Guérin (BCG), which elicits a degree of protective immunity against tuberculosis, is the most widely used vaccine in the world. Due to its persistence and immunogenicity, BCG has been proposed as a vector for vaccines against other infections, including HIV-1. BCG has a very good safety record, although it can cause disseminated disease in immunocompromised individuals. Here, we constructed a recombinant BCG vector expressing HIV-1 clade A-derived immunogen HIVA using the recently described safer and more immunogenic BCG strain AERAS-401 as the parental mycobacterium. Using routine ex vivo T-cell assays, BCG.HIVA(401) as a stand-alone vaccine induced undetectable and weak CD8 T-cell responses in BALB/c mice and rhesus macaques, respectively. However, when BCG.HIVA(401) was used as a priming component in heterologous vaccination regimens together with recombinant modified vaccinia virus Ankara-vectored MVA.HIVA and ovine atadenovirus-vectored OAdV.HIVA vaccines, robust HIV-1-specific T-cell responses were elicited. These high-frequency T-cell responses were broadly directed and capable of proliferation in response to recall antigen. Furthermore, multiple antigen-specific T-cell clonotypes were efficiently recruited into the memory pool. These desirable features are thought to be associated with good control of HIV-1 infection. In addition, strong and persistent T-cell responses specific for the BCG-derived purified protein derivative (PPD) antigen were induced. This work is the first demonstration of immunogenicity for two novel vaccine vectors and the corresponding candidate HIV-1 vaccines BCG.HIVA(401) and OAdV.HIVA in nonhuman primates. These results strongly support their further exploration.