Allorecognition, the ability to distinguish ‘self’ from ‘non-self’ based on allelic differences at allorecognition loci, is common in all domains of life. Allorecognition restricts the opportunities for social parasitism, and is therefore crucial for the evolution of cooperation. However, the maintenance of allorecognition diversity provides a paradox. If allorecognition is costly relative to cooperation, common alleles will be favored. Thus, the cost of allorecognition may reduce the genetic variation upon which allorecognition crucially relies, a prediction now known as ‘Crozier's paradox’. We establish the relative costs of allorecognition, and their consequences for the short-term evolution of recognition labels theoretically predicted by Crozier. We use fusion among colonies of the fungus Neurospora crassa, regulated by highly variable allorecognition genes, as an experimental model system. We demonstrate that fusion among colonies is mutually beneficial, relative to absence of fusion upon allorecognition. This benefit is due not only to absence of mutual antagonism, which occurs upon allorecognition, but also to an increase in colony size per se. We then experimentally demonstrate that the benefit of fusion selects against allorecognition diversity, as predicted by Crozier. We discuss what maintains allorecognition diversity.