The spatial dynamics of criminal activities has been recently studied through statistical physics methods; however, models and results have been focusing on local scales (city level) and much less is known about these patterns at larger scales, e.g. at a country level. Here we report on a characterization of the spatial dynamics of the homicide crimes along the Brazilian territory using data from all cities (~5000) in a period of more than thirty years. Our results show that the spatial correlation function in the per capita homicides decays exponentially with the distance between cities and that the characteristic correlation length displays an acute increasing trend in the latest years. We also investigate the formation of spatial clusters of cities via a percolation-like analysis, where clustering of cities and a phase-transition–like behavior describing the size of the largest cluster as a function of a homicide threshold are observed. This transition-like behavior presents evolutive features characterized by an increasing in the homicide threshold (where the transitions occur) and by a decreasing in the transition magnitudes (length of the jumps in the cluster size). We believe that our work sheds new light on the spatial patterns of criminal activities at large scales, which may contribute for better political decisions and resources allocation as well as opens new possibilities for modeling criminal activities by setting up fundamental empirical patterns at large scales.