The association between the myrmecophyte Triplaris and ants of the genus Pseudomyrmex is an often-reported example of mutualism but no molecular studies have examined this association to date. In this study, the interspecific relationships of Triplaris were reconstructed using five molecular markers (two chloroplast and three nuclear), and the relationships of the associated Pseudomyrmex using two molecular regions (one mitochondrial and one nuclear). A data set including all known collections of plant hosts and resident ants was also compiled. The pattern of distribution of both organisms reveals that there are varying degrees of host specificity; most ants show broader host usage (promiscuous) but one species (P. dendroicus) is faithful to a single species of Triplaris. In most ant-plant interactions, host usage is not specific at the species level and preferences may result from geographical or ecological sorting. The specificity of P. dendroicus could be based on chemical recognition of the host they were raised on.