Much of the current literature on state failure and collapse suffers from serious conceptual flaws. It ignores the variegated types of empirical statehood that exist on the ground, it conflates the absence of a central government with anarchy, it creates an unhelpful distinction between lsquoaccomplishedrsquo and lsquofailedrsquo states, and it is guided by a teleological belief in the convergence of all nation-states. Particularly African states figure prominently in this debate and are frequently portrayed in almost pathological terms. Proposing a comparative analysis of politics in the Somali inhabited territories of the Horn of Africa, this article challenges state failure discourses on both theoretical and empirical grounds. We draw attention to the multiple processes of state-building and forms of statehood that have emerged in Somalia, and the neighbouring Somalia region of Ethiopia, since 1991. The analysis of the different trajectories of these Somali political orders reveals that state formation in Africa contradicts central tenets of the state failure debate and that external state-building interventions should recognise and engage with sub-national political entities.