The European Union’s political and economic integration project has always raised questions about its legitimacy, effectiveness, and shared values. While effectiveness may be considered as a yardstick to justify actions, it also opens up a larger debate on whether effectiveness alone is sufficient to ensure legitimacy or whether something else is needed in the long run. In the field of European criminal law, such a discussion assumes particular relevance, since the use of force has always been a core competence of nation-states. The paper explores traditional justifying methods for the use of criminal sanctions relied upon by the nation-state in the EU supranational context. By looking at the so-called utilitarian and deontological methods, where the legitimising factor is respectively the efficacy of an action or the ‘rightness’ of the incrimination, it devotes its efforts to understanding which form of legitimacy the European Union should adopt in view of further integration. Drawing from this analysis, it explores the application of the European Arrest Warrant. The latter relies on the principle of Mutual Recognition. Although the underlying rationale of Mutual Recognition is aimed at effectiveness, this cannot work without ‘mutual trust’ between MS. Mutual trust, however, presupposes a shared understanding of values, so a paradox arises. Efficiency cannot be fully achieved in this area without a common basis of values. The paper finally explores the case of Carles Puigdemont as an emblematic example of how, in the criminal law domain, probably a mixed approach to legitimacy is needed.