Malaria is a global human parasitic disease mainly caused by the protozoon Plasmodium falciparum. Increased parasite resistance to current drugs determines the relevance of finding new treatments against new targets. A novel target is the M1 alanyl-aminopeptidase from P. falciparum (PfA-M1), which is essential for parasite development in human erythrocytes and is inhibited by the pseudo-peptide bestatin. In this work, we used a combinatorial multicomponent approach to produce a library of peptidomimetics and screened it for the inhibition of recombinant PfA-M1 (rPfA-M1) and the in vitro growth of P. falciparum erythrocytic stages (3D7 and FcB1 strains). Dose-response studies with selected compounds allowed identifying the bestatin-based peptidomimetic KBE009 as a submicromolar rPfA-M1 inhibitor (Ki=0.4μM) and an in vitro antimalarial compound as potent as bestatin (IC50=18μM; without promoting erythrocyte lysis). At therapeutic-relevant concentrations, KBE009 is selective for rPfA-M1 over porcine APN (a model of these enzymes from mammals), and is not cytotoxic against HUVEC cells. Docking simulations indicate that this compound binds PfA-M1 without Zn2+ coordination, establishing mainly hydrophobic interactions and showing a remarkable shape complementarity with the active site of the enzyme. Moreover, KBE009 inhibits the M1-type aminopeptidase activity (Ala-7-amido-4-methylcoumarin substrate) in isolated live parasites with a potency similar to that of the antimalarial activity (IC50=82μM), strongly suggesting that the antimalarial effect is directly related to the inhibition of the endogenous PfA-M1. These results support the value of this multicomponent strategy to identify PfA-M1 inhibitors, and make KBE009 a promising hit for drug development against malaria.