As a legal-constitutional system of government of fairly rigid rules and practices, federalism in Africa might not have a positive image, but the overall relevance and utility of federalism for state-building on the continent has been grossly underestimated, for reasons related to narrow legal-constitutional standards. This paper shows that federal solutions offer the relevant framework and principles for rebuilding the state as a decolonial construct of collective ownership, shared rule and self-rule. The central argument is that the unravelling of the received state, whose failure is manifest in the contestations, conflicts and wars, and overall inability to function as a state, provides the opportunity for renegotiating and re-bargaining the state.