This essay is intended to analyze the debate on the withdrawal from the ICC by African states. First, it examines the background of the debate. Second, it carefully looks at the contents of the Withdrawal Strategy Document by the AU. In so doing, this essay illustrates the nature of the issue as the dilemmas between politics and law, peace and justice, and regionalism and universalism. There is a general growing trend of multi-layered security structures of international society in relation to the principles of local ownership, empowerment and partnership. The essay argues that there is room for the ICC’s endeavors to advance “positive complementarity.”