A combined measles-malaria vaccine containing different attenuated recombinant measles-malaria vectors comprising a heterologous nucleic acid encoding several Plasmodium falciparum antigens is described. Preferably, it relates to viral vectors that comprise nucleic acids encoding the circumsporozoite (CS) protein of P. falciparum, the merozoite surface protein 1 (MSP-1) of P. falciparum, and its derivatives (p-42; p-83-30-38) in its glycosylated and secreted forms, and apical membrane antigen1 (AMA1) of P. falciparum, in 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.