This chapter examines the relations between the European Union (EU) and North Atlantic Treaty Organization (NATO) in their counter-piracy operations off the Horn of Africa by scrutinizing two interconnected phases of these operations. The political phase comprising the political decision to launch these initiatives; and the tactical phase capturing the in-theatre interaction between the EU and NATO. The chapter sets out the context for the maritime operations launched by NATO and the EU, providing a brief chronological outline of the ascendancy of piracy as a global economic and security threat, and of the corresponding international response. It discusses the main body of the analysis and is organized around the different phases. In principle, both the EU and NATO agreed that an effective counter-piracy strategy involved a holistic mix of instruments, as well as cooperation with a wide network of actors, both offshore and on land.