Malaria remains a significant global health burden and a vaccine would make a substantial contribution to malaria control. Chimpanzee Adenovirus 63 Modified Vaccinia Ankara Multiple epitope thrombospondin adhesion protein (ME-TRAP) and vaccination has shown significant efficacy against malaria sporozoite challenge in malaria-naive European volunteers and against malaria infection in Kenyan adults. Infants are the target age group for malaria vaccination; however, no studies have yet assessed T-cell responses in children and infants. We enrolled 138 Gambian and Burkinabe children in four different age-groups: 2–6 years old in The Gambia; 5–17 months old in Burkina Faso; 5–12 months old, and also 10 weeks old, in The Gambia; and evaluated the safety and immunogenicity of Chimpanzee Adenovirus 63 Modified Vaccinia Ankara ME-TRAP heterologous prime-boost immunization. The vaccines were well tolerated in all age groups with no vaccine-related serious adverse events. T-cell responses to vaccination peaked 7 days after boosting with Modified Vaccinia Ankara, with T-cell responses highest in 10 week-old infants. Heterologous prime-boost immunization with Chimpanzee Adenovirus 63 and Modified Vaccinia Ankara ME-TRAP was well tolerated in infants and children, inducing strong T-cell responses. We identify an approach that induces potent T-cell responses in infants, which may be useful for preventing other infectious diseases requiring cellular immunity.