The evolution of multicellularity enabled specialization of cells, but required novel signalling mechanisms for regulating cell differentiation. Early multicellular organisms are mostly extinct and the origins of these mechanisms are unknown. Here using comparative genome and transcriptome analysis across eight uni- and multicellular amoebozoan genomes, we ﬁnd that 80% of proteins essential for the development of multicellular Dictyostelia are already present in their unicellular relatives. This set is enriched in cytosolic and nuclear proteins, and protein kinases. The remaining 20%, unique to Dictyostelia, mostly consists of extracellularly exposed and secreted proteins, with roles in sensing and recognition, while several genes for synthesis of signals that induce cell-type specialization were acquired by lateral gene transfer. Across Dictyostelia, changes in gene expression correspond more strongly with phenotypic innovation than changes in protein functional domains. We conclude that the transition to multicellularity required novel signals and sensors rather than novel signal processing mechanisms.