The sophisticated methodologies for the identification of customary international law by the ad hoc tribunals led to major developments in the field of international criminal law including the prosecution of war crimes in non-international armed conflicts, the development of new criminal acts and the creation of novel modes of liability. These findings also gave rise to criticism for possible infringements to the principle of legality. These concerns were arguably put to rest with the advent of the codified moment and the adoption of the Rome Statute of the International Criminal Court (ICC). Under this new paradigm, customary international law was given the marginal role of lacuna-filling. This study revisits these conclusions and reveals that, upon closer examination, there are several chinks in the armor of the Rome Statute through which customary international law may still be applied, both as a lacuna-filling device and as a source of law in its own right. While this may not be problematic per se, an analysis of the emerging jurisprudence of the Court shows that the judges have engaged in the problematic methodological approaches for the identification of custom that characterized the ad hoc tribunals. By doing so, the ICC may sacrifice the principle of legality. As a solution to this problem, this work suggests the return to traditional methodologies for the identification of norms of customary international law based on the evidence of state practice and opinio juris. This, it is argued, will not only protect the principle of legality but it will also contribute to the achievement of the goals of international criminal law.