Altruistic cooperation has enabled humans to thrive1. However, the interaction of sentient individuals faces the dilemma of limiting the downsides of personally beneficial, but globally detrimental selfish behavior without causing even more damage through escalating conflicts. The evolution of cooperation has been studied in non-zero sum games, with the Prisoner’s Dilemma, “the E. coli of social psychology”2, providing a fundamental test case. Typically3-12, interactions between individuals may (i) occur repeatedly, (ii) involve groups of individuals, (iii) be subject to evolutionary mechanisms, often based on the study of equilibria for homogeneous settings.13 However, a better understanding of the non-equilibrium dynamics of cooperation in structured environments is crucial for further progress. Here we consider an inhomogeneous, spatial, dynamic setting, in which evolution occurs not necessarily at an equilibrium. We demonstrate how minimal, publicly observable information on previous behavior can be exploited to outperform alternatives, achieving evolutionary performance similar to clandestine, membership-based strategies. We also show how polarization (with a cooperating population disintegrating into competing factions) and tribalism (with cooperation solely based on group membership instead of behavior) can arise, how these phenomena can be overcome with two additional mechanisms, and how cooperation can erode. Our results demonstrate how cooperation, reputation, polarization and tribalism are intricately linked, even in a simple mathematical model in which they arise in absence of complex psychological mechanisms. This provides a fundamental explanation for how robust cooperation may break down when faced with eroding universality of globally recognized values and of local, direct reciprocity; it may also help to prevent behavior-based reputation systems from giving way to emergent polarization and, ultimately, purely membership-based tribalism. We also anticipate that our methods will be of critical importance for the design and implementation of artificial structures based on the interaction of many independent, self-interested virtual agents.