This chapter explores the evolving dynamics of sovereignty and legitimacy among Armed Non-State Actors (ANSAs) in the Middle East and North Africa (MENA), challenging the dominant state-centric international order. Using Ann Stilz’s theory of “territorial sovereignty”—which requires rightful occupancy, basic justice, and collective self-determination—as a normative benchmark, the chapter evaluates the governance claims of MENA ANSAs such as Hamas, Hezbollah, the Houthis, and Kurdish actors. Complementing this with Stepputat’s framework of “emerging governscapes,” it categorizes ANSAs into red, brown, and grey zones based on their interactions with national state structures. The analysis reveals that many ANSAs exercise substantial political authority and can claim limited sovereignty due to their capacity to uphold essential governance functions and cultivate internal legitimacy. Drawing on empirical cases, the chapter argues for a reconceptualization of sovereignty in fragile contexts, emphasizing the need for indigenous understandings of governance, particularly in postcolonial, conflict-ridden societies. It concludes by calling for a more inclusive international legal and political framework that acknowledges ANSAs as de facto political entities in contemporary global order.