Understanding and controlling the surface adhesion of pathogenic bacteria is of urgent biomedical importance. However, many aspects of this process remain unclear (for example, microscopic details of the initial adhesion and possible variations between individual cells). Using a new high-throughput method, we identify and follow many single cells within a clonal population of Escherichia coli near a glass surface. We find strong phenotypic heterogeneities: A fraction of the cells remain in the free (planktonic) state, whereas others adhere with an adhesion strength that itself exhibits phenotypic heterogeneity. We explain our observations using a patchy colloid model; cells bind with localized, adhesive patches, and the strength of adhesion is determined by the number of patches: Nonadherers have no patches, weak adherers bind with a single patch only, and strong adherers bind via a single or multiple patches. We discuss possible implications of our results for controlling bacterial adhesion in biomedical and other applications.