The protein-protein interaction between the human CMG2 receptor and the Bacillus anthracis protective antigen (PA) is essential for the transport of anthrax lethal and edema toxins into human cells. We used a genetically encoded high throughput screening platform to screen a SICLOPPS library of 3.2 million cyclic hexapeptides for inhibitors of this protein-protein interaction. Unusually, the top 3 hits all contained stop codons in the randomized region of the library, resulting in linear rather than cyclic peptides. These peptides disrupted the targeted interaction in vitro; two act by binding to CMG2 while one binds PA. The efficacy of the most potent CMG2-binding inhibitor was improved through the incorporation of non-natural phenylalanine analogues. Cell based assays demonstrated that the optimized inhibitor protects macrophages from the toxicity of lethal factor.