The Neotropical myrmecophytic tree Cordia alliodora hosts symbiotic Azteca ants in most of its widespread range. The taxonomy of the genus Azteca is notoriously difficult, which has frequently obscured species identity in ecological studies. We used sequence data from one mitochondrial and four nuclear loci to infer phylogenetic relationships, patterns of geographic distribution, and timing of diversification for 181 colonies of Azteca from Mexico to Colombia. We identified at least eight lineages of C. alliodora-dwelling Azteca, including at least five lineages within the most abundant and specialized species, Azteca pittieri. Mitochondrial and nuclear data were concordant at the species level, but not within species; comparison of the two datasets suggested that both introgression and incomplete lineage sorting contributed to these inconsistencies. Divergence time analyses estimated that C. alliodora-dwelling Azteca shared a common ancestor approximately 9-18 million years ago, coinciding with arid climatic conditions that favored their primary habitat, seasonally dry tropical forests. Significant differentiation not correlated with geographic distance was found among the five lineages of A. pittieri, which suggests limited historical gene flow among geographically restricted populations. This contrasts with the previously reported lack of phylogeographic structure in the host tree. Climatic niches, and particularly precipitation-related variables, did not overlap between the sites occupied by northern and southern lineages of A. pittieri. Together, these results suggest that restricted gene flow among ant populations may facilitate local adaptation to environmental heterogeneity. Differences in evolvability between the ants and their host trees may affect the evolutionary stability of this widespread ant-plant mutualism.