A generic approach to inducing high level CD8+ T cell responses would be of value for prophylactic and therapeutic immunisation against several infectious diseases. However, it has been very difficult to achieve such immune responses using available vaccination strategies. Malaria is one of several diseases against which a new generation of better CD8+ T cell-inducing vaccines might be useful and is unusual in that it allows assessment of vaccine efficacy in small numbers of volunteers in carefully controlled challenge studies. Here we review the identification of a heterologous prime-boost regime using DNA priming and recombinant modified vaccinia Ankara (MVA) boosting that induces high level T cell responses in both mice and non-human primates. Clinical trials to determine whether this prime-boost approach is immunogenic in humans are in progress.