Bacterial cell envelope protein (CEP) complexes mediate a range of processes, including membrane assembly, antibiotic resistance and metabolic coordination. However, only limited characterization of relevant macromolecules has been reported to date. Here we present a proteomic survey of 1,347 CEPs encompassing 90% inner- and outer-membrane and periplasmic proteins of Escherichia coli. After extraction with non-denaturing detergents, we affinity-purified 785 endogenously tagged CEPs and identified stably associated polypeptides by precision mass spectrometry. The resulting high-quality physical interaction network, comprising 77% of targeted CEPs, revealed many previously uncharacterized heteromeric complexes. We found that the secretion of autotransporters requires translocation and the assembly module TamB to nucleate proper folding from periplasm to cell surface through a cooperative mechanism involving the β-barrel assembly machinery. We also establish that an ABC transporter of unknown function, YadH, together with the Mla system preserves outer membrane lipid asymmetry. This E. coli CEP 'interactome' provides insights into the functional landscape governing CE systems essential to bacterial growth, metabolism and drug resistance.