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.