A new class of cysteine protease inhibitors based on fumaric acid derived oligopeptides was successfully identified from a high-throughput screening of a solid-phase bound combinatorial library. As target enzymes falcipain and rhodesain were used, which play important roles in the life cycles of the parasites which cause malaria (Plasmodium falciparum) and African sleeping sickness (Trypanosoma brucei rhodesiense). The best inhibitors with unusual amino acid sequences not reported before for this type of enzyme were also fully analyzed in detail in solution. Ki values in the lower micromolar and even nanomolar region were found. Some inhibitors are even active against plasmodia and show good selectivity relative to other enzymes. Also the mechanism of action was studied and could be shown to be irreversible inhibition.