The advent of complex multicellularity (CM) was a pivotal event in the evolution of animals, plants and fungi. In the fungal Ascomycota, CM is based on hyphal filaments and arose in the Pezizomycotina. The genus Neolecta defines an enigma: phylogenetically placed in a related group containing mostly yeasts, Neolecta nevertheless possesses Pezizomycotina-like CM. Here we sequence the Neolecta irregularis genome and identify CM-associated functions by searching for genes conserved in Neolecta and the Pezizomycotina, which are absent or divergent in budding or fission yeasts. This group of 1,050 genes is enriched for functions related to diverse endomembrane systems and their organization. Remarkably, most show evidence for divergence in both yeasts. Using functional genomics, we identify new genes involved in fungal complexification. Together, these data show that rudimentary multicellularity is deeply rooted in the Ascomycota. Extensive parallel gene divergence during simplification and constraint leading to CM suggest a deterministic process where shared modes of cellular organization select for similarly configured organelle- and transport-related machineries.