Bacillus anthracis is a causative agent of anthrax. Anthrax toxins are composed of a protective antigen (PA), lethal factor (LF), and edema factor (EF), in which the PA is a central mediator for the delivery of the two enzymatic moieties LF and EF. Therefore, the PA has been an attractive target in the prevention and vaccinization for anthrax toxin. Recently, it has been reported that the molecule consisting of multiple copies of PA-binding peptide, covalently linked to a flexible polymer backbone, blocked intoxification of anthrax toxin in an animal model. In the present study, we have screened novel diverse peptides that bind to PA with a high affinity (picomolar range) from an M13 peptide display library and characterized the binding regions of the peptides. Our works provide a basis to develop novel potent inhibitors or diagnostic probes with a diverse polyvalence.