Explaining altruistic cooperation is one of the greatest challenges faced by sociologists, economists, and evolutionary biologists. The problem is determining why an individual would carry out a costly behavior that benefits another. Possible solutions to this problem include kinship, repeated interactions, and policing. Another solution that has recently received much attention is the threat of punishment. However, punishing behavior is often costly for the punisher, and so it is not immediately clear how costly punishment could evolve. We use a direct (neighbor-modulated) fitness approach to analyze when punishment is favored. This methodology reveals that, contrary to previous suggestions, relatedness between interacting individuals is not crucial to explaining cooperation through punishment. In fact, increasing relatedness directly disfavors punishing behavior. Instead, the crucial factor is a positive correlation between the punishment strategy of an individual and the cooperation it receives. This could arise in several ways, such as when facultative adjustment of behavior leads individuals to cooperate more when interacting with individuals who are more likely to punish. More generally, our results provide a clear example of how the fundamental factor driving the evolution of social traits is a correlation between social partners and how this can arise for reasons other than genealogical kinship.