Evolutionary adaptations for maintaining beneficial microbes are hallmarks of mutualistic evolution. Fungus-farming "attine" ant species have complex cuticular modifications and specialized glands that house and nourish antibiotic-producing Actinobacteria symbionts, which in turn protect their hosts' fungus gardens from pathogens. Here we reconstruct ant-Actinobacteria evolutionary history across the full range of variation within subtribe Attina by combining dated phylogenomic and ultramorphological analyses. Ancestral-state analyses indicate the ant-Actinobacteria symbiosis arose early in attine-ant evolution, a conclusion consistent with direct observations of Actinobacteria on fossil ants in Oligo-Miocene amber. qPCR indicates that the dominant ant-associated Actinobacteria belong to the genus Pseudonocardia Tracing the evolutionary trajectories of Pseudonocardia-maintaining mechanisms across attine ants reveals a continuum of adaptations. In Myrmicocrypta species, which retain many ancestral morphological and behavioral traits, Pseudonocardia occur in specific locations on the legs and antennae, unassociated with any specialized structures. In contrast, specialized cuticular structures, including crypts and tubercles, evolved at least three times in derived attine-ant lineages. Conspicuous caste differences in Pseudonocardia-maintaining structures, in which specialized structures are present in worker ants and queens but reduced or lost in males, are consistent with vertical Pseudonocardia transmission. Although the majority of attine ants are associated with Pseudonocardia, there have been multiple losses of bacterial symbionts and bacteria-maintaining structures in different lineages over evolutionary time. The early origin of ant-Pseudonocardia mutualism and the multiple evolutionary convergences on strikingly similar anatomical adaptations for maintaining bacterial symbionts indicate that Pseudonocardia have played a critical role in the evolution of ant fungiculture.