Recent events have created an urgent need for new therapeutic strategies to treat anthrax. We have applied a mixture-based peptide library approach to rapidly determine the optimal peptide substrate for the anthrax lethal factor (LF), a metalloproteinase with an important role in the pathogenesis of the disease. Using this approach we have identified peptide analogs that inhibit the enzyme in vitro and that protect cultured macrophages from LF-mediated cytolysis. The crystal structures of LF bound to an optimized peptide substrate and to peptide-based inhibitors provide a rationale for the observed selectivity and may be exploited in the design of future generations of LF inhibitors.