Apical membrane antigen 1 (AMA1) of the malaria parasite Plasmodium falciparum has been implicated in the invasion of host erythrocytes and is an important vaccine candidate. We have previously described a 20-residue peptide, R1, that binds to AMA1 and subsequently blocks parasite invasion. Because this peptide appears to target a site critical for AMA1 function, it represents an important lead compound for anti-malarial drug development. However, the effectiveness of this peptide inhibitor was limited to a subset of parasite isolates, indicating a requirement for broader strain specificity. Furthermore, a barrier to the utility of any peptide as a potential therapeutic is its susceptibility to rapid proteolytic degradation. In this study, we sought to improve the proteolytic stability and AMA1 binding properties of the R1 peptide by systematic methylation of backbone amides (N-methylation). The inclusion of a single N-methyl group in the R1 peptide backbone dramatically increased AMA1 affinity, bioactivity, and proteolytic stability without introducing global structural alterations. In addition, N-methylation of multiple R1 residues further improved these properties. Therefore, we have shown that modifications to a biologically active peptide can dramatically enhance activity. This approach could be applied to many lead peptides or peptide therapeutics to simultaneously optimize a number of parameters.