Objective/context: In this paper, we describe the evolution of municipality-level homicide rates, during the 2003-2014 period in Colombia. Methodology: Quantitative analysis with multi-level regression models and finite-mix models. Conclusions: Our results show an important and statistically significant reduction of violence at the national level, and a large variability across geographical areas. We identify an association between profiles of change and a general government performance index, which provides support to the hypothesis of a differentiated State across time and space, and motives further studies and differential public policies across municipalities. Originality: The relationship between homicidal violence and the role of the State has been commonly analyzed on an aggregated level that ignores the disaggregated territorial view and heterogeneity of microterritorial realities. This article recognizes the local differences for the design of public policies that reflect contextual realities and assume that the performance of the State is heterogeneous and not static.