Malaria is a major global health problem for which an effective vaccine is required urgently. Prime-boost vaccination regimes involving plasmid DNA and recombinant modified vaccinia virus Ankara-encoding liver-stage malaria antigens have been shown to be powerfully immunogenic for T cells and capable of inducing partial protection against experimental malaria challenge in humans, manifested as a delay in time to patent parasitemia. Here, we report that substitution of plasmid DNA as the priming vector with a specific attenuated recombinant fowlpox virus, FP9, vaccine in such prime-boost regimes can elicit complete sterile protection that can last for 20 months. Protection at 20 months was associated with persisting memory but not effector T cell responses. The protective efficacy of various immunization regimes correlated with the magnitude of induced immune responses, supporting the strategy of maximizing durable T cell immunogenicity to develop more effective liver-stage vaccines against Plasmodium falciparum malaria.