Gram-negative bacteria are surrounded by a protective outer membrane (OM) with phospholipids in its inner leaflet and lipopolysaccharides (LPS) in its outer leaflet. The OM is also populated with many β-barrel outer-membrane proteins (OMPs), some of which have been shown to cluster into supramolecular assemblies. However, it remains unknown how abundant OMPs are organized across the entire bacterial surface and how this relates to the lipids in the membrane. Here, we reveal how the OM is organized from molecular to cellular length scales, using atomic force microscopy to visualize the OM of live bacteria, including engineered strains and complemented by specific labeling of abundant OMPs. We find that a predominant OMP in the OM, the porin OmpF, forms a near-static network across the surface, which is interspersed with barren patches of LPS that grow and merge with other patches during cell elongation. Embedded within the porin network is OmpA, which forms noncovalent interactions to the underlying cell wall. When the OM is destabilized by mislocalization of phospholipids to the outer leaflet, a new phase appears, correlating with bacterial sensitivity to harsh environments. We conclude that the OM is a mosaic of phase-separated LPS-rich and OMP-rich regions, the maintenance of which is essential to the integrity of the membrane and hence to the lifestyle of a gram-negative bacterium.