The article examines the links between paramilitary groups and the Colombian state within a context of pervasive violence. Colombia represents a particularly interesting case as high-intensity violence is accompanied by the preservation of a relatively strong institutional framework. Most interpretations of this relationship consider it to be either a sign of state weakness or a centralized strategy to outsource violence. Taking a different stance, the paper argues that the existence of paramilitary groups compels us to analyze government through practices vis-à-vis the treatment of violence. A policy linking private security and counterinsurgency, crafted in the early 1990s and known as Convivir, provides an illustration of this approach.