Abstract Hamilton's rule explains when natural selection will favor altruism between conspecifics, given their degree of relatedness. In practice, indicators of relatedness (such as scent) coevolve with strategies based on these indicators, a fact not included in previous theories of kin recognition. Using a combination of simulation modeling and mathematical extension of Hamilton's rule, we demonstrate how altruism can emerge and be sustained in a coevolutionary setting where relatedness depends on an individual's social environment and varies from one locus to another. The results support a very general expectation of widespread, and not necessarily weak, conditional altruism in nature.