Establishment of multicellularity represents a major transition in eukaryote evolution. A subgroup of Amoebozoa, the dictyosteliids, has evolved a relatively simple aggregative multicellular stage resulting in a fruiting body supported by a stalk. Protosteloid amoeba, which are scattered throughout the amoebozoan tree, differ by producing only one or few single stalked spores. Thus, one obvious difference in the developmental cycle of protosteliids and dictyosteliids seems to be the establishment of multicellularity. To separate spore development from multicellular interactions, we compared the genome and transcriptome of a Protostelium species (Protostelium aurantium var. fungivorum) with those of social and solitary members of the Amoebozoa. During fruiting body formation nearly 4,000 genes, corresponding to specific pathways required for differentiation processes, are upregulated. A comparison with genes involved in the development of dictyosteliids revealed conservation of >500 genes, but most of them are also present in Acanthamoeba castellanii for which fruiting bodies have not been documented. Moreover, expression regulation of those genes differs between P. aurantium and Dictyostelium discoideum. Within Amoebozoa differentiation to fruiting bodies is common, but our current genome analysis suggests that protosteliids and dictyosteliids used different routes to achieve this. Most remarkable is both the large repertoire and diversity between species in genes that mediate environmental sensing and signal processing. This likely reflects an immense adaptability of the single cell stage to varying environmental conditions. We surmise that this signaling repertoire provided sufficient building blocks to accommodate the relatively simple demands for cell-cell communication in the early multicellular forms.