Outer membrane proteins (OMPs) produced by Gram-negative bacteria contain a cylindrical amphipathic β-sheet (“β-barrel”) that functions as a membrane spanning domain. The assembly (folding and membrane insertion) of OMPs is mediated by the heterooligomeric β-barrel assembly machine (BAM). The central BAM subunit (BamA) is an attractive antibacterial target because its structure and cell surface localization are conserved, it catalyzes an essential reaction, and potent bactericidal compounds that inhibit its activity have been described. Here we utilize mRNA display to discover cyclic peptides that bind to Escherichia coli BamA with high affinity. We describe three peptides that arrest the growth of BAM deficient E. coli strains, inhibit OMP assembly in live cells and in vitro, and bind to unique sites within the BamA β-barrel lumen. Remarkably, we find that if the peptides are added to cultures after a slowly assembling OMP mutant binds to BamA, they accelerate its biogenesis. The data strongly suggest that the peptides trap BamA in conformations that block the initiation of OMP assembly but favor a later assembly step. Molecular dynamics simulations provide further evidence that the peptides bind stably to BamA and function by a previously undescribed mechanism.