We previously reported that a recombinant pantothenate auxotroph of Mycobacterium bovis BCG expressing human immunodeficiency virus type 1 (HIV-1) subtype C Gag (rBCGpan-Gag) efficiently primes the mouse immune system for a boost with a recombinant modified vaccinia virus Ankara (rMVA) vaccine. In this study, we further evaluated the immunogenicity of rBCGpan-Gag in a nonhuman primate model. Two groups of chacma baboons were primed or mock primed twice with either rBCGpan-Gag or a control BCG. Both groups were boosted with HIV-1 Pr55(gag) virus-like particles (Gag VLPs). The magnitude and breadth of HIV-specific cellular responses were measured using a gamma interferon (IFN-γ) enzyme-linked immunosorbent spot (ELISPOT) assay, and the cytokine profiles and memory phenotypes of T cells were evaluated by polychromatic flow cytometry. Gag-specific responses were detected in all animals after the second inoculation with rBCGpan-Gag. Boosting with Gag VLPs significantly increased the magnitude and breadth of the responses in the baboons that were primed with rBCGpan-Gag. These responses targeted an average of 12 Gag peptides per animal, compared to an average of 3 peptides per animal for the mock-primed controls. Robust responses of Gag-specific polyfunctional T cells capable of simultaneously producing IFN-γ, tumor necrosis alpha (TNF-α), and interleukin-2 (IL-2) were detected in the rBCGpan-Gag-primed animals. Gag-specific memory T cells were skewed toward a central memory phenotype in both CD4(+) and CD8(+) T cell populations. These data show that the rBCGpan-Gag prime and Gag VLP boost vaccine regimen is highly immunogenic, inducing a broad and polyfunctional central memory T cell response. This report further indicates the feasibility of developing a BCG-based HIV vaccine that is safe for childhood HIV immunization.