Aggregative multicellularity requires the ability of cells to recognise conspecifics. Social amoebae are among the best studied of such organisms, but the mechanism and evolutionary background of species recognition remained to be investigated. Here we show that heterologous expression of a single Dictyostelium purpureum gene is sufficient for D. discoideum cells to efficiently make chimaeric fruiting bodies with D. purpureum cells. This gene forms a bidirectional pair with another gene on the D. purpureum genome, and they are both highly polymorphic among independent wild isolates of the same mating group that do not form chimaeric fruiting bodies with each other. These paired genes are both structurally similar to D. discoideum tgrB1/C1 pair, which is responsible for clonal discrimination within that species, suggesting that these tgr genes constitute the species recognition system that has attained a level of precision capable of discriminating between clones within a species. Analysis of the available genome sequences of social amoebae revealed that such gene pairs exist only within the clade composed of species that produce precursors of sterile stalk cells (prestalk cells), suggesting concurrent evolution of a precise allorecognition system and a new 'worker' cell-type dedicated to transporting and supporting the reproductive cells.