This article examines the interaction between politics and informal institutions of order in two of Africa’s most violent and crime-ridden cities, Nairobi, Kenya and Lagos, Nigeria. In both cities, governments have failed to provide basic public services and security to citizens, especially to those who reside in informal settlements or slums. A variety of informal institutions, including ethnic militia and block-level vigilante groups, fulfill security and enforcement roles in these relatively ungoverned urban spaces. This article examines the differences in the character and organization of these “specialists in violence,” and it argues that these differences are often integrally linked to the political strategies and aims of elites. The article makes two primary contributions to existing understandings of informal order in violent cities in the developing world. First, I find that organizations seemingly organically linked to local communities, such as ethnic militia, are strongly influenced by national-level political struggles. Violent organizations can gain a foothold and degree of legitimacy by appealing to traditional loyalties, including ethnicity, but organizations with these advantages are also attractive targets for cooptation by political actors. Secondly, both direct state repression and electoral use of militia lead to more predatory forms of interaction between these groups and local communities.