A distinguishing feature of humans is our ability to intentionally create rules that support social order, and modify existing rules when social or ecological conditions change. Cultural evolution leads to much more rapid change in the social and ecological environment that humans occupy compared to genetic evolution, suggesting that the need to change and adapt norms would have been a constant pressure on human societies. The main theory in the cultural evolution framework for how group-beneficial change in norms can happen is cultural group selection, whereby competition between groups that have different norms and institutions leads preferentially to the spread of norms and institutions that increase the success of the cultural group. But cultural group selection cannot explain rapid changes in norms within groups, as it can operate only on existing variation among groups. We posit that over millennia cultural group selection acted not just on norms, but crucially also on normative infrastructure – the meta-norms that structure a group’s processes for classifying and enforcing norms, favoring infrastructures with combinations of stability and innovativity that aid the success of the cultural group. By regulating the process by which violations are reasoned about, ambiguities are resolved, situations lacking precedence are evaluated, and enforcement behaviors are calibrated, normative infrastructure can shape how existing norms are interpreted and re-imagined, and how new norms get created to deal with novel circumstances. We conducted vignette experiments, surveys, and semi-structured interviews to elicit the normative infrastructure of the Turkana, a pastoral society in Kenya in which social order is maintained informally. Here we present results from the vignette studies showing how Turkana normative infrastructure resembles or differs from legal order, a broad class of solutions that permit rapid innovation without loss in stability.