The system established by the statute of the International Criminal Court (ICC) is founded on the principle of complementarity, i.e. that the ICC complements national legal systems. As such, conceptually, the Court is a support system and system of last resort for when domestic systems are ‘unwilling or unable’ to undertake accountability. This develops the argument that progress in addressing mass atrocities in Africa should be seen in increments not in quantum leaps. As such, this article seeks to reconstruct a regional trajectory of accountability for mass atrocities in Africa with evidence grounded in both state practice and the histories of African countries. It argues that such historically grounded narrative is essential if the mission of international justice in Africa is not to be misplaced. Contrary to popular narrative which tends to suggest that Africa’s institutions have tolerated these atrocities, this paper marshals considerable historical evidence to suggest that African institutions have, over time, made considerable progress in discouraging them through different forms of accountability. It explores different ways in which these regional efforts can be supported by looking beyond the ICC and re-imagining international justice.