Legal philosophers have long debated the question, what is law? But few in social science have attempted to explain the phenomenon of legal order. In this article, we build a rational choice model of legal order in an environment that relies exclusively on decentralized enforcement, such as we find in human societies prior to the emergence of the nation state and inmanymodern settings.Wedemonstrate thatwecan support an equilibrium in which wrongful behavior is effectively deterred by exclusively decentralized enforcement, specifically collective punishment. Equilibrium is achieved by an institution that supplies a common logic for classifying behavior as wrongful or not. We argue that several features ordinarily associated with legal order—such as generality, impersonality, open process, and stability—can be explained by the incentive and coordination problems facing collective punishment.