The role of the European Union’s (EU) criminal law enforcement agencies in the fight against cross-border crimes have progressively increased over the past few decades. Thus, the traditional viewpoint that law enforcement in the EU is an exclusive matter for national authorities has almost been abandoned. Although the EU’s criminal law enforcement agencies represent an important step forward in the path of an increasing integration, their main shortcoming stems from the lack of EU-wide rules of substantive and procedural criminal law. Such lack makes their activities dependent on, and constrained by, national laws. This paper suggests that the increasing role of the EU’s law enforcement agencies should proceed hand in hand with the efforts for approximation of the national criminal laws of the Member States. Furthermore, additional mechanisms that offer the European law enforcement agencies adequate guidance at the European Convention on Human Rights standards are needed to allow EU citizens to truly enjoy their rights to free movement.