The nature of the maritime environment presents unique challenges for countering criminal and terrorist activity. Often overlooked in the literature, multilateral capacity building approaches offer lessons for developing more sustainable security architectures and resilience within coastal states, which are both the source and solution to countering extremism, criminality and terrorism in maritime spaces long term. This paper firstly examines the crossovers between maritime piracy, terrorism and other forms of maritime criminality as context to understanding the transferability of approaches. Next, maritime security capacity building projects launched by international organizations in the western Indian Ocean are briefly discussed, highlighting pertinent activities and innovative approaches. Finally, lessons from these projects are extracted and discussed within the context of maritime terrorism.