The threat of transnational maritime crimes has grown significantly in the past few years, particularly in the Gulf of Aden, due to the ongoing armed conflicts in the Middle East and Africa combined with the concomitant deteriorated diplomatic relations between states in the region. This background context has enabled organized groups to commit their crimes largely with impunity, benefiting from poor international cooperation between states in criminal matters. This article sets out the international legal framework on transnational maritime crimes and the internationally recognized definitions of major maritime crimes. It then takes the Republic of Djibouti as a case example of how the international legal framework has been incorporated into domestic legislation and assesses its enforcement in practice. The article identifies an underlying lack of international cooperation in criminal matters in respect of prosecuting transnational maritime crimes, particularly with regard to mutual legal assistance and extradition not only in respect of Djibouti but also in the Gulf of Aden as a whole. Based also on evidence gathered by one of the authors during a United Nations Office of Drugs and Crime’s workshop that took place in the Djibouti Regional Maritime Training Centre in November 2022, the article concludes that, in order to protect the peace and security of the region and implement the UN 2030 Agenda for Sustainable Development, states must enhance cooperation by entering into further bilateral as well as plurilateral agreements on cooperation in criminal matters. More importantly, in order to enhance mutual understanding, trust and the sharing of good practices, it is recommended that a judicial cooperation network in the Gulf of Aden and the Red Sea under the auspices of the United Nations Office of Drugs and Crime Global Maritime Crime Programme be established.