Eumaeus butterflies are obligate herbivores of Zamia, the most diverse neotropical genus of cycads. Eumaeus-Zamia interactions have been characterized mainly for species distributed in North and Central America. However, larval host plant use by the southern Eumaeus clade remains largely unknown, precluding a comprehensive study of co-evolution between the genera. Here, we combine fieldwork with museum and literature surveys to expand herbivory records for Eumaeus from 21 to 38 Zamia species. We inferred a time-calibrated phylogeny of Eumaeus to test for distinct macroevolutionary scenarios of larval host plant conservatism and co-evolution. We found a remarkable coincidence between Eumaeus and Zamia diversification, with the butterfly stem group diverging at the same time as the most recent radiation of Zamia in the Miocene. Cophylogenetic reconciliation analyses show a strong cophylogenetic signal between cycads and their butterfly herbivores. Bipartite model-based approaches indicate that this is because closely related Zamia species are used by the same Eumaeus species, suggesting larval host plant resource tracking by the butterfly herbivores. Our results highlight a case of tight evolution between Eumaeus butterflies and cycads, pointing to the generality of correlated evolution and phylogenetic tracking in plant-herbivore interactions across seed plants.