Coevolution between flowering plants and their pollinators is thought to have generated much of the diversity of life on Earth, but the population processes that may have produced these macroevolutionary patterns remain unclear. Mathematical models of coevolution in obligate pollination mutualisms suggest that phenotype matching between plants and their pollinators can generate reproductive isolation. Here, we test this hypothesis using a natural experiment that examines the role of natural selection on phenotype matching between yuccas and yucca moths (Tegeticula spp.) in mediating reproductive isolation between two varieties of Joshua tree (Yucca brevifolia var. brevifolia and Y. brevifolia var. jaegeriana). Using passive monitoring techniques, DNA barcoding, microsatellite DNA genotyping, and sibship reconstruction, we track host specificity and the fitness consequences of host choice in a zone of sympatry. We show that the two moth species differ in their degree of host specificity and that oviposition on a foreign host plant results in the production of fewer offspring. This difference in host specificity between the two moth species mirrors patterns of chloroplast introgression from west to east between host varieties, suggesting that natural selection acting on pollinator phenotypes mediates gene flow and reproductive isolation between Joshua-tree varieties.