In this article, we discuss the advantages and progress made with heterologous prime-boost vaccination strategies. Although the consecutive use of DNA and recombinant viral vectors induce greatly enhanced and sustained levels of both cell-mediated and humoral immunity in preclinical models, the results have not yet been translated to clinical use. Despite this, there is still a high level of optimism that these strategies offer the best hope for the development of vaccines against diseases for which there are no effective vaccines currently available. In this article, we discuss how prime-boost immunization can elicit improved mucosal immunity, how 'mucosal' regimes also elicit 'high-quality' (high-avidity) T-cell responses to vaccine antigens, and the use of cytokines/chemokines as genetic adjuvants.