Small macrocyclic peptides are promising candidates for new anti-infective drugs. To date, such peptides have been poorly studied in the context of anti-virulence targets. Using phage display and a self-designed peptide library, we identified a cyclic heptapeptide that can bind the carbon storage regulator A (CsrA) from Yersinia pseudotuberculosis and displace bound RNA. This disulfide-bridged peptide, showed an IC50 value in the low micromolar range. Upon further characterization, cyclisation was found to be essential for its activity. To increase metabolic stability, a series of disulfide mimetics were designed and a redox-stable 1,4-disubstituted 1,2,3-triazole analogue displayed activity in the double-digit micromolar range. Further experiments revealed that this triazole peptidomimetic is also active against CsrA from Escherichia coli and RsmA from Pseudomonas aeruginosa. This study provides an ideal starting point for medicinal chemistry optimization of this macrocyclic peptide and might pave the way towards broad-acting virulence modulators.