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. To address this issue, we measure the phenotype and chemotactic performance of tens of thousands of individual, freely-swimming Escherichia coli as they climbed a gradient of attractant. Spatial structure spontaneously emerged from initially well-mixed wild type populations due to non-genetic diversity. By manipulating the expression of chemotaxis proteins, we established a causal relationship between protein expression, non-genetic diversity, and performance that was theoretically predicted. This approach generated a phenotype-to-performance map, in which we found a nonlinear regime. We used this map to demonstrate how the shape of a phenotypic distribution can have as large of an effect on performance as changing the mean phenotype, suggesting that evolution could act on both during the process of adaptation.