Hyphae represent a hallmark structure of multicellular fungi. The evolutionary origins of hyphae and of the underlying genes are, however, hardly known. By systematically analyzing 72 complete genomes, we here show that hyphae evolved early in fungal evolution probably via diverse genetic changes, including co-option and exaptation of ancient eukaryotic (e.g. phagocytosis-related) genes, the origin of new gene families, gene duplications and alterations of gene structure, among others. Contrary to most multicellular lineages, the origin of filamentous fungi did not correlate with expansions of kinases, receptors or adhesive proteins. Co-option was probably the dominant mechanism for recruiting genes for hypha morphogenesis, while gene duplication was apparently less prevalent, except in transcriptional regulators and cell wall - related genes. We identified 414 novel gene families that show correlated evolution with hyphae and that may have contributed to its evolution. Our results suggest that hyphae represent a unique multicellular organization that evolved by limited fungal-specific innovations and gene duplication but pervasive co-option and modification of ancient eukaryotic functions.