The Escherichia coli chemotaxis network is a model system for biological signal processing. In E. coli, transmembrane receptors responsible for signal transduction assemble into large clusters containing several thousand proteins. These sensory clusters have been observed at cell poles and future division sites. Despite extensive study, it remains unclear how chemotaxis clusters form, what controls cluster size and density, and how the cellular location of clusters is robustly maintained in growing and dividing cells. Here, we use photoactivated localization microscopy (PALM) to map the cellular locations of three proteins central to bacterial chemotaxis (the Tar receptor, CheY, and CheW) with a precision of 15 nm. We find that cluster sizes are approximately exponentially distributed, with no characteristic cluster size. One-third of Tar receptors are part of smaller lateral clusters and not of the large polar clusters. Analysis of the relative cellular locations of 1.1 million individual proteins (from 326 cells) suggests that clusters form via stochastic self-assembly. The super-resolution PALM maps of E. coli receptors support the notion that stochastic self-assembly can create and maintain approximately periodic structures in biological membranes, without direct cytoskeletal involvement or active transport.