This contribution traces the importance of traditional institutions in rehabilitating societies in general terms and more particularly in post-independence Uganda. The current regime, partly by inventing “traditional” cultural institutions, partly by co-opting them for its own interests, contributed to a loss of legitimacy of those who claim responsibility for customary law. More recently, international prosecutions have complicated the use of customary mechanisms within such societies. This article shows that some traditional and cultural leaders continue to struggle to restore their original institutions, some having taken the initiative of inventing new forms of engaging with society. Uganda is presented as a test case for the International Criminal Court’s ability to work with traditional judicial institutions in Africa.