Abstract Biological functions are typically performed by groups of cells that express predominantly the same genes, yet display a continuum of phenotypes. While it is known how one genotype can generate such non‐genetic diversity, it remains unclear how different phenotypes contribute to the performance of biological function at the population level. We developed a microfluidic device to simultaneously measure the phenotype and chemotactic performance of tens of thousands of individual, freely swimming Escherichia coli as they climbed a gradient of attractant. We discovered that spatial structure spontaneously emerged from initially well‐mixed wild‐type populations due to non‐genetic diversity. By manipulating the expression of key chemotaxis proteins, we established a causal relationship between protein expression, non‐genetic diversity, and performance that was theoretically predicted. This approach generated a complete phenotype‐to‐performance map, in which we found a nonlinear regime. We used this map to demonstrate how changing the shape of a phenotypic distribution can have as large of an effect on collective performance as changing the mean phenotype, suggesting that selection could act on both during the process of adaptation.