Some politicians engage in relationships with criminal actors in pursuit of mutual interests. How does their rise to power affect state capacity? I focus on one of Colombia’s worst episodes of criminal politics to understand how the victory of paramilitary-friendly mayors impacted subnational taxation. Focusing on close races, I find that the victory of a paramilitary-friendly mayor in 2007 led to a substantive drop in property taxation in subsequent years. I argue that criminal collusion allows politicians and criminals to accumulate wealth and political power, but doing so requires them to deliberately undermine local state institutions. Indeed, the evidence suggests that municipalities governed by paramilitary-friendly politicians experienced a weakening of property rights, the worsening of local judicial institutions, and an alteration of the electoral playing field. Rather than a mere consequence of criminal collusion, state weakening is a politically strategic decision that serves the interests of both criminals and politicians.