This paper discusses maritime security in the Mediterranean, beginning, as current dynamics mainly result from long-term historical developments, by examining the evolving security situation in the Mediterranean and the interplay of littoral and outside actors that culminated in U.S.-Soviet confrontation in the Cold War. The paper demonstrates how the end of the Cold War has increased the relative geostrategic importance of the Mediterranean, with new maritime security issues such as terrorism from the sea, drug trafficking, and illegal immigration becoming more important. This paper analyzes maritime security and naval cooperation in the Mediterranean in this current context, examining the relevance and capabilities of both NATO and the EU. It concludes by discussing, from both a European and a transatlantic perspective, the multi-directional and multi-dimensional challenges facing maritime security cooperation in the Mediterranean.