Protection against liver-stage malaria relies on the induction of high frequencies of antigen-specific CD8⁺ T cells. We have previously reported high protective levels against mouse malaria, albeit short-lived, by a single vaccination with adenoviral vectors coding for a liver-stage antigen (ME.TRAP). Here, we report that prime-boost regimens using modified vaccinia virus Ankara (MVA) and adenoviral vectors encoding ME.TRAP can enhance both short- and long-term sterile protection against malaria. Protection persisted for at least 6 months when simian adenoviruses AdCh63 and AdC9 were used as priming vectors. Kinetic analysis showed that the MVA boost made the adenoviral-primed T cells markedly more polyfunctional, with the number of gamma interferon (INF-γ), tumor necrosis factor alpha (TNF-α), and interleukin-2 (IL-2) triple-positive and INF-γ and TNF-α double-positive cells increasing over time, while INF-γ single-positive cells declined with time. However, IFN-γ production prevailed as the main immune correlate of protection, while neither an increase of polyfunctionality nor a high integrated mean fluorescence intensity (iMFI) correlated with protection. These data highlight the ability of optimized viral vector prime-boost regimens to generate more protective and sustained CD8⁺ T-cell responses, and our results encourage a more nuanced assessment of the importance of inducing polyfunctional CD8⁺ T cells by vaccination.