Most bacteria live in colonies, where they often express different cell types. The ecological significance of these cell types and their evolutionary origin are often unknown. Here, we study the evolution of cell differentiation in the context of surface colonization. We particularly focus on the evolution of a sticky cell type that is required for surface attachment, but is costly to express. The sticky cells not only facilitate their own attachment, but also that of non-sticky cells. Using individual-based simulations, we show that surface colonization rapidly evolves and in most cases leads to phenotypic heterogeneity, in which sticky and non-sticky cells occur side by side on the surface. In the presence of regulation, cell differentiation leads to a remarkable set of bacterial life cycles, in which cells alternate between living in the liquid and living on the surface. The dominant life stage is formed by the surface-attached colony that shows many complex features: colonies reproduce via fission and by producing migratory propagules, cells inside the colony divide labour, and colonies can produce filaments to facilitate expansion. Overall, our model illustrates how the evolution of an adhesive cell type goes hand in hand with the evolution of complex bacterial life cycles. 