Het idee voor zo'n hof of tribunaal was niet nieuw. Al in 1872 wilde de Zwitser Gustav Moynier een hof om de wandaden van de Frans-Pruisische oorlog van 1870 te veroordelen. Ook het Verdrag van Versailles (1919) bood de mogelijkheid om een internationaal strafhof een oordeel te laten vellen over de Duitse keizer Wilhelm II. Zo'n tribunaal kwam er niet.
De gruwelen van de Tweede Wereldoorlog brachen de internationale gemeenschap tot een Genocide Verdrag (1948). Op grond van dit verdrag worden handelingen die tot doel hebben bepaalde nationale, etnische en religieuze groeperingen uit te roeien, als internationaal misdrijf bestempeld. In dit verdrag werd de berechting van dergelijke misdrijven door een internationaal hof voorzien. Ook op het gebied van het humanitaire oorlogsrecht werden na 1945 de regels voor de behandeling van burgers in oorlogstijd aangescherpt. Deze ontwikkelingen waren voor de Commissie voor Internationaal Recht (International Law Commission, ILC) van de Verenigde Naties aanleiding om een permanent Internationaal Strafhof te bepleiten, maar de plannen liepen in de jaren vijftig vast wegens de Koude Oorlog.
De val van de Berlijnse Muur in 1989 leverde een nieuwe impuls op om een permanent strafhof te verwezenlijken. De ILC stelde op verzoek van VN in 1994 een ontwerp-statuut op.
Begin 1993 werd op initiatief van de VN-Veiligheidsraad het Joegoslavië-tribunaal opgericht voor de berechting van oorlogsmisdadigers in het vroegere Joegoslavië. Een jaar later besloot de Veiligheidsraad tot de oprichting van een tribunaal voor de berechting van de gruwelen van 1993 in Rwanda. Deze beide tribunalen zijn ad-hoc tribunalen die er niet waren geweest als er een internationaal strafhof zou functioneren.
In 1996 stelde het zogenoemde Voorbereidend Comité (PrepCom ICC) een tekst op voor een statuut over de instelling van een internationaal strafhof. Op de Rome-Conferentie, 1998, kwam het statuut van het International Criminal Court tot stand. Er waren zestig ratificaties nodig voor de inwerkingtreding van het statuut. Die grens werd op 11 april bereikt, toen tien landen tegelijk hun ratificatie neerlegden bij de VN.