Colony formation was the first step towards evolution of multicellularity in many macroscopic organisms. Dictyostelid social amoebas have used this strategy for over 600 Myr to form fruiting structures of increasing complexity. To understand in which order multicellular complexity evolved, we measured 24 phenotypic characters over 99 dictyostelid species. Using phylogenetic comparative methods, we show that the last common ancestor (LCA) of Dictyostelia probably erected small fruiting structures directly from aggregates. It secreted cAMP to coordinate fruiting body morphogenesis, and another compound to mediate aggregation. This phenotype persisted up to the LCAs of three of the four major groups of Dictyostelia. The group 4 LCA co-opted cAMP for aggregation and evolved much larger fruiting structures. However, it lost encystation, the survival strategy of solitary amoebas that is retained by many species in groups 1–3. Large structures, phototropism and a migrating intermediate ‘slug’ stage coevolved as evolutionary novelties within most groups. Overall, dictyostelids show considerable plasticity in the size and shape of multicellular structures, both within and between species. This probably reflects constraints placed by colonial life on developmental control mechanisms, which, depending on local cell density, need to direct from 10 to a million cells into forming a functional fructification.