A fundamental goal of biology is to understand how novel phenotypes evolved through changes in existing genes. The Dictyostelia or social amoebas represent a simple form of multicellularity, where starving cells aggregate to build fruiting structures. This review summarizes efforts to provide a framework for investigating the genetic changes that generated novel morphologies in the Dictyostelia. The foundation is a recently constructed molecular phylogeny of the Dictyostelia, which was used to examine trends in the evolution of novel forms and in the divergence of genes that shape these forms. There is a major trend towards the formation of large unbranched fruiting bodies, which is correlated with the use of cyclic AMP (cAMP) as a secreted signal to coordinate cell aggregation. The role of cAMP in aggregation arose through co-option of a pathway that originally acted to coordinate fruiting body formation. The genotypic changes that caused this innovation and the role of dynamic cAMP signaling in defining fruiting body size and pattern throughout social amoeba evolution are discussed.