Successful future HIV vaccines are expected to generate an effective cellular and humoral response against the virus in both the peripheral blood and mucosal compartments. We previously reported the development of DNA-C and MVA-C vaccines based on HIV-1 subtype C and demonstrated their immunogenicity when given in a DNA prime-MVA boost combination in a nonhuman primate model. In the current study, rhesus macaques previously vaccinated with a DNA-C and MVA-C vaccine regimen were re-vaccinated 3.5years later with MVA-C followed by a protein vaccine based on HIV-1 subtype C envelope formulated with MF59 adjuvant (gp140Env/MF59), and finally a concurrent boost with both vaccines. A single MVA-C re-vaccination elicited T cell responses in all animals similar to previous peak responses, with 4/7 demonstrating responses >1000 SFU/106 PBMC. In contrast to an Env/MF59-only vaccine, concurrent boosting with MVA-C and Env/MF59 induced HIV-specific cellular responses in multiple mucosal associated lymph nodes in 6/7 animals, with high magnitude responses in some animals. Both vaccine regimens induced high titer Env-specific antibodies with ADCC activity, as well as neutralization of Tier 1 viruses and modest Tier 2 neutralization. These data demonstrate the feasibility of inducing HIV-specific immunity in the blood and mucosal sites of viral entry by means of DNA and poxvirus-vectored vaccines, in combination with a HIV envelope-based protein vaccine.