The principle of legality (Article 49 Charter) is a cornerstone of criminal justice systems and has a long history in the European legal order. It has four aspects: it prohibits retroactivity, analogical interpretation, vagueness and reliance on custom in criminal law. Many of its functions find application in European law. Concomitantly, several inconsistencies and shortcomings are observed. Its application to mutual recognition is effectively excluded and the same goes for rules on jurisdiction. These two lacunae cause uncertainty in the cross-border application of criminal law. Moreover, the CJEU has sought to restrict its application to limitation rules, but with contradicting reasoning. Three significant challenges are identified in this chapter: the multilevel criminal justice created by the institutional arrangements of the European legal order; the everlasting conflict between due process and crime control observed in European criminal policy; and the lack of defined theoretical rationales and values justifying the principle of legality.