Gram-negative bacteria have a cell envelope that comprises an outer membrane (OM), a peptidoglycan (PG) layer and an inner membrane (IM)1. The OM and PG are load-bearing, selectively permeable structures that are stabilized by cooperative interactions between IM and OM proteins2,3. In Escherichia coli, Braun's lipoprotein (Lpp) forms the only covalent tether between the OM and PG and is crucial for cell envelope stability4; however, most other Gram-negative bacteria lack Lpp so it has been assumed that alternative mechanisms of OM stabilization are present5. We used a glycoproteomic analysis of PG to show that β-barrel OM proteins are covalently attached to PG in several Gram-negative species, including Coxiella burnetii, Agrobacterium tumefaciens and Legionella pneumophila. In C. burnetii, we found that four different types of covalent attachments occur between OM proteins and PG, with tethering of the β-barrel OM protein BbpA becoming most abundant in the stationary phase and tethering of the lipoprotein LimB similar throughout the cell cycle. Using a genetic approach, we demonstrate that the cell cycle-dependent tethering of BbpA is partly dependent on a developmentally regulated L,D-transpeptidase (Ldt). We use our findings to propose a model of Gram-negative cell envelope stabilization that includes cell cycle control and an expanded role for Ldts in covalently attaching surface proteins to PG.