Cheaters disrupt cooperation by reaping the benefits without paying their fair share of associated costs. Cheater impact can be diminished if cooperators display a tag ('greenbeard') and recognise and preferentially direct cooperation towards other tag carriers. Despite its popular appeal, the feasibility of such greenbeards has been questioned because the complex patterns of partner-specific cooperative behaviours seen in nature require greenbeards to come in different colours. Here we show that a locus ('Tgr') of a social amoeba represents a polychromatic greenbeard. Patterns of natural Tgr locus sequence polymorphisms predict partner-specific patterns of cooperation by underlying variation in partner-specific protein-protein binding strength and recognition specificity. Finally, Tgr locus polymorphisms increase fitness because they help avoid potential costs of cooperating with incompatible partners. These results suggest that a polychromatic greenbeard can provide a key mechanism for the evolutionary maintenance of cooperation.