Background: The safety and immunogenicity of a vaccine regimen consisting of a 6-plasmid HIV-1 DNA prime (envA, envB, envC, gagB, polB, nefB) boosted by a recombinant adenovirus serotype-5 (rAd5) HIV-1 with matching inserts was evaluated in HIV-seronegative participants from South Africa, United States, Latin America and the Caribbean. Methods: 480 participants were evenly randomized to receive either: DNA (4 mg IM by Biojector) at 0, 1 and 2 months, followed by rAd5 (10 10 PU IM by needle/syringe) at 6 months; or placebo. Participants were monitored for reactogenicity and adverse events throughout the 12-month study. Peak and duration of HIV-specific humoral and cellular immune responses were evaluated after the prime and boost. Results: The vaccine was well tolerated and safe. T-cell responses, detected by interferon-γ (IFN-γ) ELISpot to global potential T-cell epitopes (PTEs) were observed in 70.8% (136/192) of vaccine recipients overall, most frequently to Gag (54.7%) and to Env (54.2%). In U.S. vaccine recipients T-cell responses were less frequent in Ad5 sero-positive versus sero-negative vaccine recipients (62.5% versus 85.7% respectively, p = 0.035). The frequency of HIV-specific CD4+ and CD8+ T-cell responses detected by intracellular cytokine staining were similar (41.8% and 47.2% respectively) and most secreted ≥2 cytokines. The vaccine induced a high frequency (83.7%-94.6%) of binding antibody responses to consensus Group M, and Clades A, B and C gp140 Env oligomers. Antibody responses to Gag were elicited in 46% of vaccine recipients. Conclusion: The vaccine regimen was well-tolerated and induced polyfunctional CD4+ and CD8+ T-cells and multi-clade anti-Env binding antibodies. Trial Registration: ClinicalTrials.gov NCT00125970.