Falcipain-2 and falcipain-3 are papain-family cysteine proteases of the malaria parasite Plasmodium falciparum that are responsible for host hemoglobin hydrolysis to provide amino acids for parasite protein synthesis. Different heteroarylnitrile derivatives were studied as potential falcipain inhibitors and therefore potential antiparasitic lead compounds, with the 5-substituted-2-cyanopyrimidine chemical class emerging as the most potent and promising lead series. Through a sequential lead optimization process considering the different positions present in the initial scaffold, nanomolar and subnanomolar inhibitors at falcipains 2 and 3 were identified, with activity against cultured parasites in the micromolar range. Introduction of protonable amines within lead molecules led to marked improvements of up to 1000 times in activity against cultured parasites without noteworthy alterations in other SAR tendencies. Optimized compounds presented enzymatic activities in the picomolar to low nanomolar range and antiparasitic activities in the low nanomolar range.