Currently, there are more than 30 million people infected with HIV-1 and thousands more are infected each day. Vaccination is the single most effective mechanism for prevention of viral disease, and after more than 25 years of research, one vaccine has shown somewhat encouraging results in an advanced clinical efficacy trial. A modified intent-to-treat analysis of trial results showed that infection was approximately 30% lower in the vaccine group compared to the placebo group. The vaccine was administered using a heterologous prime-boost regimen in which both target antigens and delivery vehicles were changed during the course of inoculations. Here we examine the complexity of heterologous prime-boost immunizations. We show that the use of different delivery vehicles in prime and boost inoculations can help to avert the inhibitory effects caused by vector-specific immune responses. We also show that the introduction of new antigens into boost inoculations can be advantageous, demonstrating that the effect of `original antigenic sin' is not absolute. Pre-clinical and clinical studies are reviewed, including our own work with a three-vector vaccination regimen using recombinant DNA, virus (Sendai virus or vaccinia virus) and protein. Promising preliminary results suggest that the heterologous prime-boost strategy may possibly provide a foundation for the future prevention of HIV-1 infections in humans.