The present invention relates to a combined measles-malaria vaccine containing different attenuated recombinant measles-malaria vectors comprising a heterologous nucleic acid encoding several Plasmodium falciparum antigens. Preferably, it relates to viral vectors that comprise nucleic acids encoding the circumsporozoite (CS) protein of P . falciparum, the merozoite surface protein 1 (MSP-I) of P. falciparum, and its derivatives (p-42; p-83-30-38) in its glycosylated and secreted forms, and apical membrane antigen 1 (AMA1) of P . falciparum, and its anchored or secreted form. The viral vector stems from an attenuated measles virus, based on a strain that is used as a vaccine and is efficient in delivering the gene of interest and that binds to and infects the relevant immune cells efficiently. In a preferred embodiment, the CS, the MSP1 and the AMA1 proteins are generated from the virus such that they will give rise to a potent immune response in mammals, preferably humans; the expression of the proteins is elevated due to human codon optimisation. Furthermore, the invention relates to the use of the recombinant vaccine in the prophylactic treatment of malaria.