Centuries of artificial selection have dramatically improved the yield of human agriculture; however, strong directional selection also occurs in natural symbiotic interactions. Fungus-growing attine ants cultivate basidiomycete fungi for food. One cultivar lineage has evolved inflated hyphal tips (gongylidia) that grow in bundles called staphylae, to specifically feed the ants. Here we show extensive regulation and molecular signals of adaptive evolution in gene trancripts associated with gongylidia biosynthesis, morphogenesis and enzymatic plant cell wall degradation in the leaf-cutting ant cultivar Leucoagaricus gongylophorus. Comparative analysis of staphylae growth morphology and transcriptome-wide expressional and nucleotide divergence indicate that gongylidia provide leaf-cutting ants with essential amino acids and plant-degrading enzymes, and that they may have done so for 20-25 million years without much evolutionary change. These molecular traits and signatures of selection imply that staphylae are highly advanced coevolutionary organs that play pivotal roles in the mutualism between leaf-cutting ants and their fungal cultivars.