Challenges in the development of an effective HIV-1 vaccine are myriad with significant hurdles posed by viral diversity, the lack of a human correlate of protection and difficulty in creating immunogens capable of eliciting broadly neutralizing antibodies. The implicit requirement for novel approaches to these problems has resulted in vaccine candidates designed to elicit cellular and/or humoral immune responses, to include recombinant DNA, viral and bacterial vectors, and subunit proteins. Here, we review data from clinical studies primarily of poxvirus and adenovirus vector vaccines, used in a heterologous prime-boost combination strategy. Currently, this strategy appears to hold the most promise for an effective vaccine based on results from immunogenicity testing and nonhuman primate challenge models, as well as the modest efficacy recently observed in the Thai prime-boost trial.