The notion that states pursue a monopoly over the use of force rings increasingly hollow. From vigilantes that patrol the United States’ southern border, to thugs for hire in China, states are characterized by non-state violent actors. These trends are more pronounced in comparatively lower-capacity states. Employing the concept of “security assemblages,” I propose that it is crucial to consider historically embedded relations among violent actors and institutions in order to understand their socio-political role and implications for state authority. This approach offers three insights: first, in low-capacity states, violence is not zero-sum. Rather, it is assembled among diverse actors, which each have historically embedded comparative advantages. Second, therefore, state efforts to monopolize violence should be taken as an empirical question rather than an assumption grounding analysis. Third, relationships between violent actors occur in thick institutional environments, meaning that violent actors, including state actors and institutions, often must act under significant constraints. To illustrate these points, I conduct a mixed-methods nested study of vigilantes in Uganda, finding that vigilantes are more common where other authorities are present, and are more helpful when other authorities are also more helpful. Focusing on dynamics between vigilantes and police, I pinpoint their historically distinct roles: the police were established as a colonial-era institution to suppress political dissent, while vigilantes have long been socially embedded actors tasked with everyday security provision. Thus, in this case, police and vigilantes are not substitutes; instead they play distinct and complementary roles.