Critical maritime infrastructure protection has become a priority in ocean governance, particularly in Europe. Increased geopolitical tensions, regional conflicts, and the Nord Stream pipeline attacks in the Baltic Sea of September 2022 have been the main catalysts for this development. Calls for enhancing critical maritime infrastructure protection have multiplied, yet, what this implies in practice is less clear. This is partially a question of engineering and risk analysis. It also concerns how the multitude of actors involved can act concertedly. Dialogue, information sharing, and coordination are required, but there is a lack of discussion about which institutional set ups would lend themselves. In this article, we argue that the maritime counter-piracy operations off Somalia, as well as maritime cybersecurity governance hold valuable lessons to provide new answers for the institutional question in the critical maritime infrastructure protection agenda. We start by clarifying what is at stake in the CMIP agenda and why it is a major contemporary governance challenge. We then examine and assess the instruments found in maritime counter-piracy and maritime cybersecurity governance, including why and how they provide effective solutions for enhancing critical maritime infrastructure protection. Finally, we assess the ongoing institution building for CMIP in Europe. While we focus on the European experience, our discussion on designing institutions carries forward lessons for CMIP in other regions, too.