Macro-historical changes in the practices and structures of organized violence have their own regularities that require theoretical analysis. It is shown that the steady growth and development of these structures are determined by the main trends of social evolution such as demographic growth, the expansion and complication of polities, and the development of technologies and weapons. The internal mechanisms of both the cyclicality and the direction and irreversibility of these changes are considered. The practices of organized violence have changed considerably, and many of those unacceptable today were once common, socially approved, and even obligatory. Hypothetical principles have been formulated for the emergence, spread, and termination of such practices, which are always connected with the nature and outcome of political struggle, as well as with the change of worldviews consisting of primarily moral, social and political values and corresponding normative principles. The inevitable costs of the growth of violence structures are associated primarily with the possibility of their leaders gaining political subjectivity and claims to power, which is fraught with conspiracies, revolts, and similar phenomena that undermine social and political stability. These costs generate concerns of the rulers and elites to control the violence structures. Three basic forms of such control have been described as “ideal types”, those of patrimonial-charismatic control based on emotional commitment to the ruler, conflict-repressive control with divide-and-conquer strategies, and bureaucratic control involving subordination to formal rules. The last type includes two versions, with a reliance on the principle of power and on the principle of law. The social and mental foundations that support the rule of law in institutions and organizations of state violence are examined.