This contribution discusses the importance of trust for cooperation in criminal justice in the European Union. As a result of Schengen and the open borders within Europe, the freedom of movement comes sometimes in conflict with the fight against crime and terrorism. Political considerations often favour mutual recognition and criminal-justice cooperation over legislative harmonisation of national laws and regulations. Increasing trust between the EU member states in criminal law is difficult because criminal justice systems have remained nationally anchored. Herlin-Karnell recommends that the EU give greater weight to the proportionality principle in criminal justice cases. The EU Charter of Fundamental Rights and the European Convention on Human Rights represent the minimum requirements for EU legislation and greater attention to those documents increase trust in the system.