Mutualisms are balanced antagonistic interactions where both species gain a net benefit. Because mutualisms generate resources, they can be exploited by individuals that reap the benefits of the interaction without paying any cost. The presence of such ‘cheaters’ may have important consequences, yet we are only beginning to understand how cheaters evolve from mutualists and how their evolution may be curtailed within mutualistic lineages. The yucca–yucca moth pollination mutualism is an excellent model in this context as there have been two origins of cheating from within the yucca moth lineage. We used nuclear and mitochondrial DNA markers to examine genetic structure in a moth population where a cheater species is parapatric with a resident pollinator. The results revealed extensive hybridization between pollinators and cheaters. Hybrids were genetically intermediate to parental populations, even though all individuals in this population had a pollinator phenotype. The results suggest that mutualisms can be stable in the face of introgression of cheater genes and that the ability of cheaters to invade a given mutualism may be more limited than previously appreciated.