Many states in Latin America, Africa and Asia lack the monopoly of violence, identified by Max Weber as the foundation of the state, and thus the capacity to govern effectively. In this paper we develop a new perspective on the establishment of the monopoly of violence and the formation of the state. We build a model to explain the incentive of central states to eliminate non-state armed actors (paramilitaries) in a democracy. The model is premised on the idea that paramilitaries may choose to and can influence elections. Since paramilitaries have preferences over policies, this reduces the incentives of the politicians they favor to eliminate them. The model also shows that while in non-paramilitary areas policies are targeted at citizens, in paramilitary controlled areas they are targeted at paramilitaries. We then investigate the predictions of our model using data from Colombia between 1991 and 2006. We first present regression and case study evidence supporting our postulate that paramilitary groups can have significant effects on elections for the legislature and the executive. Next, we show that the evidence is also broadly consistent with the implication of the model that paramilitaries tend to persist to the extent that they deliver votes to candidates for the executive whose preferences are close to theirs and that this effect is larger in areas where the Presidential candidate would have otherwise not done as well. These results illustrate that, consistent with our model, there appears to be a symbiotic relationship between some executives and paramilitaries. Finally, we use roll-call votes to illustrate a possible 'quid pro quo' between the executive and paramilitaries in Colombia. Keywords: State Capacity, Violence, Elections. JEL Classifications: D7, H11.