Acropyga ants are a widespread clade of small subterranean formicines that live in obligate symbiotic associations with root mealybugs. We generated a data set of 944 loci of ultraconserved elements (UCEs) to reconstruct the phylogeny of 41 representatives of 23 Acropyga species using both concatenation and species-tree approaches. We investigated the biogeographic history of the genus through divergence dating analyses and ancestral range reconstructions. We also explored the evolution of the Acropyga-mealybug mutualism using ancestral state reconstruction methods. We recovered a highly supported species phylogeny for Acropyga with both concatenation and species-tree analyses. The age for crown-group Acropyga is estimated to be around 30 Ma. The geographic origin of the genus remains uncertain, although phylogenetic affinities within the subfamily Formicinae point to a Paleotropical ancestor. Two main Acropyga lineages are recovered with mutually exclusive distributions in the Old World and New World. Within the Old World clade, a Palearctic and African lineage is suggested as sister to the remaining species. Ancestral state reconstructions indicate that Old World species have diversified mainly in close association with xenococcines from the genus Eumyrmococcus, although present-day associations also involve other mealybug genera. In contrast, New World Acropyga predominantly evolved with Neochavesia until a recent (10–15 Ma) switch to rhizoecid mealybug partners (genus Rhizoecus). The striking mandibular variation in Acropyga evolved most likely from a 5-toothed ancestor. Our results provide an initial evolutionary framework for extended investigations of potential co-evolutionary interactions between these ants and their mealybug partners.