Piracy off the Horn of Africa has grown substantially in recent years: 217 ships reported being attacked by Somali pirates during 2009. Although less than one percent of ships transiting the Gulf of Aden in 2009 suffered attacks, Somali piracy creates considerable economic costs and distortions. Some ships now routinely avoid the region and the estimated additional costs of specialty marine risk insurance for ships using the Gulf of Aden trade route were estimated to be in the region of US$ 400mn for 2009. International naval forces (including missions from the EU and NATO) are present in the Gulf of Aden to ensure the delivery of food aid to displaced people in Somalia, to protect shipping in the Gulf of Aden and to deter pirates from operating in the region. In our research we show that the naval presence has prevented an explosion of piracy in the Gulf of Aden, but does not appear to have had a significant deterrent effect on pirates. Some ship owners gamble that they will not be attacked and do not co-operate with the navy, thereby providing easy targets for pirates. In the meantime pirates' risk of injury, detention and trial in encounters with the navies remains relatively low. In any case sea-based naval operations will have limited success as long as Somalia remains a failed state. However, we show that partial improvements in local stability and governance are likely to increase pirate attacks. Therefore the most promising solution of the piracy problem would be to establish and fund a Somali coastguard. This would enforce both anti-piracy laws and stop illegal fishing off the coast of Somalia, providing new opportunities for economic for Somalia's coastal communities.