Sortases are transpeptidase enzymes that anchor surface proteins, including virulence factors, to the cell wall of Gram-positive bacteria, and they are potential targets for the development of anti-infective agents. While several large compound libraries were searched by high-throughput screening, no high-affinity inhibitors of sortases could be developed to date. Here, we applied phage display to screen billions of peptide macrocycles against sortase A (SrtA) of Staphylococcus aureus (S. aureus). We were able to identify potent and selective inhibitors of SrtA that blocked SrtA-mediated anchoring of synthetic substrates to the surface of live S. aureus cells. A region present in all inhibitory peptides (Leu-Pro-Pro) resembled the natural substrates of SrtA (Leu-Pro-Xaa-Thr-Gly), suggesting that the macrocycles bind to the enzyme's active site and that they form similar molecular contacts as natural substrates. The evolved peptide macrocycles may be used as lead structures for the development of potent peptidomimetic SrtA inhibitors.