For most of the past 25 years, Medellin, Colombia, has been an extreme case of complex, urban violence, involving not just drug cartels and state security forces, but also street gangs, urban guerrillas, community militias, paramilitaries, and other nonstate armed actors who have controlled micro-territories in the city's densely populated slums in ever-shifting alliances. Before 2002, Medellin's homicide rate was among the highest in the world, but after the guerrillas and militias were defeated in 2003, a major paramilitary alliance disarmed and a period of peace known as the "Medellin Miracle" began. Policy makers facing complex violence elsewhere were interested in finding out how that had happened so quickly. The research presented here is a case study of violence in Medellin over five periods since 1984 and at two levels of analysis: the city as a whole, and a sector called Caicedo La Sierra. The objectives were to describe and explain the patterns of violence, and determine whether legitimacy played any role, as the literature on social stability suggested it might. Multilevel, multidimensional frameworks for violence and legitimacy were developed to organize data collection and analysis. The study found that most decreases in violence at all levels of analysis were explained by increases in territorial control. Increases in collective (organized) violence resulted from a process of "illegitimation," in which an intolerably unpredictable living environment sparked internal opposition to local rulers and raised the costs of territorial control, increasing their vulnerability to rivals. As this violence weakened social order and the rule of law, interpersonal-communal (unorganized) violence increased. Over time, the "true believers" in armed political and social movements became marginalized or corrupted; most organized violence today is motivated by money. These findings imply that state actors, facing resurgent violence, can keep their tenuous control over the hillside slums (and other "ungoverned" areas) if they can avoid illegitimizing themselves. Their priority, therefore, should be to establish a tolerable, predictable daily living environment for local residents and businesses: other anti-violence programs will fail without strong, permanent, and respectful governance structures.