BCG vaccination against TB may also reduce malaria incidence through non-specific innate immune activation. We investigated whether giving BCG alongside an adenoviral-vectored malaria vaccine improves protection against malaria in mice. Co-immunisation broadened and strengthened the early innate cytokine responses, enabling strong CD8+ T cell-dependent protection. Our findings suggest co-immunisation with BCG and adenoviral vector as a promising strategy to combat both TB and malaria in double-endemic regions.