Over many years, we have witnessed a phenomenon known as the 'rule-of-law backsliding' process. The ongoing autocratisation of several Member States - in particular Poland and Hungary - has caused a breakdown of trust among the Community's members. These developments carry vital implications for European cooperation in criminal matters in the AFSJ. The author identifies layers and relations characterised by a lack of trust in this study. Those are analysed through the prism of the ECJ and the ECtHR jurisprudence on the issues related to the Rule of Law and mutual trust, as well as the rulings of national courts refusing to execute the EAW due to doubts regarding the legitimacy of the other Member State's judiciary. An essential point of the analysis is to highlight the paradigm shift of European constitutionalism. Lastly, an attempt is made to determine whether mutual trust constitutes sufficient grounds for developing further cooperation in criminal matters.