The evolution of complex multicellularity has been one of the major transitions in the history of life. In contrast to simple multicellular aggregates of cells, it has evolved only in a handful of lineages, including animals, embryophytes, red and brown algae, and fungi. Despite being a key step toward the evolution of complex organisms, the evolutionary origins and the genetic underpinnings of complex multicellularity are incompletely known. The development of fungal fruiting bodies from a hyphal thallus represents a transition from simple to complex multicellularity that is inducible under laboratory conditions. We constructed a reference atlas of mushroom formation based on developmental transcriptome data of six species and comparisons of >200 whole genomes, to elucidate the core genetic program of complex multicellularity and fruiting body development in mushroom-forming fungi (Agaricomycetes). Nearly 300 conserved gene families and >70 functional groups contained developmentally regulated genes from five to six species, covering functions related to fungal cell wall remodeling, targeted protein degradation, signal transduction, adhesion, and small secreted proteins (including effector-like orphan genes). Several of these families, including F-box proteins, expansin-like proteins, protein kinases, and transcription factors, showed expansions in Agaricomycetes, many of which convergently expanded in multicellular plants and/or animals too, reflecting convergent solutions to genetic hurdles imposed by complex multicellularity among independently evolved lineages. This study provides an entry point to studying mushroom development and complex multicellularity in one of the largest clades of complex eukaryotic organisms.