The goal of the EU with respect to the AFSJ is the creation of an open and secure space in a Europe, without internal borders, but with an evolving justice agenda. Transnational cooperation in these areas is based on Member States mutually trusting each other on offering a sufficient level of fundamental rights protection, which allows the mutual recognition of decisions of national authorities (judicial or not). The existence of mutual trust is therefore the cornerstone in this area, without which the operation of mutual recognition becomes dysfunctional. Mutual trust among Member States regarding the protection of fundamental rights is more often presumed or commanded by the Court rather than properly constructed, or even thoroughly checked. This crisis in the premise of mutual trust stemming from a compulsive presumption has acted to the detriment of the protection of fundamental rights. However, this is slowly changing. The paper will discuss the slow changes of this relationship in light of recent case law.