What incentives lead to the formation of states? In this paper we attempt to throw light on this question by analyzing the behavior of the Frente José Luis Zuluaga (FJLZ), a paramilitary group in the department of Antioquia, Colombia led by Luis Eduardo Zuluaga alias "McGuiver". Drawing from several data sources, including extensive fieldwork, we document how the empirical evidence about this group contradicts the most prominent theories on the origins and nature of the state. Amid the absence of the central state and their fight against guerrillas, the FJLZ tried to establish a monopoly of violence, enforced their own written legal system, raised taxes, and provided other public goods, including roads, electricity, schools and houses for the poor. They also had a bureaucratized non-clientelistic organization with functional specialization.