Gram-negative bacteria inhabit a broad range of ecological niches. For Escherichia coli, this includes river water as well as humans and animals, where it can be both a commensal and a pathogen. Intricate regulatory mechanisms ensure that bacteria have the right complement of β-barrel outer membrane proteins (OMPs) to enable adaptation to a particular habitat. Yet no mechanism is known for replacing OMPs in the outer membrane, an issue that is further confounded by the lack of an energy source and the high stability and abundance of OMPs. Here we uncover the process underpinning OMP turnover in E. coli and show it to be passive and binary in nature, in which old OMPs are displaced to the poles of growing cells as new OMPs take their place. Using fluorescent colicins as OMP-specific probes, in combination with ensemble and single-molecule fluorescence microscopy in vivo and in vitro, as well as molecular dynamics simulations, we established the mechanism for binary OMP partitioning. OMPs clustered to form ∼0.5-μm diameter islands, where their diffusion is restricted by promiscuous interactions with other OMPs. OMP islands were distributed throughout the cell and contained the Bam complex, which catalyses the insertion of OMPs in the outer membrane. However, OMP biogenesis occurred as a gradient that was highest at mid-cell but largely absent at cell poles. The cumulative effect is to push old OMP islands towards the poles of growing cells, leading to a binary distribution when cells divide. Hence, the outer membrane of a Gram-negative bacterium is a spatially and temporally organized structure, and this organization lies at the heart of how OMPs are turned over in the membrane.