Interspecific mutualisms have been playing a central role in the functioning of all ecosystems since the early history of life. Yet the theory of coevolution of mutualists is virtually nonexistent, by contrast with well-developed coevolutionary theories of competition, predator-prey and host-parasite interactions. This has prevented resolution of a basic puzzle posed by mutualisms: their persistence in spite of apparent evolutionary instability. The selective advantage of 'cheating', that is, reaping mutualistic benefits while providing fewer commodities to the partner species, is commonly believed to erode a mutualistic interaction, leading to its dissolution or reciprocal extinction. However, recent empirical findings indicate that stable associations of mutualists and cheaters have existed over long evolutionary periods. Here, we show that asymmetrical competition within species for the commodities offered by mutualistic partners provides a simple and testable ecological mechanism that can account for the long-term persistence of mutualisms. Cheating, in effect, establishes a background against which better mutualists can display any competitive superiority. This can lead to the coexistence and divergence of mutualist and cheater phenotypes, as well as to the coexistence of ecologically similar, but unrelated mutualists and cheaters.