The risk for seabed security threats in the Baltic Sea has increased significantly in the last decade, with constant doubtful maritime accidents that resulted in broken communication cables laid on the ocean floor, leading to enormous financial losses. Marine sabotage crimes affecting multiple nations, require the development of a regional maritime transport policy, addressing seabed security threats based on a regional agreement and respective convention, since any policy must be implemented under the rule of law. This paper analyses the development of a regional agreement for cooperation in maritime security, among all the affected States in the Baltic, to protect critical marine infrastructure with the expansion of the Convention on the Protection of the Marine Environment of the Baltic Sea Area (the “Helsinki Convention”) and the respective Baltic Marine Environment Protection Commission – also known as the “Helsinki Commission” or “HELCOM” as established in 1974 pursuant to this Convention to include maritime security. The authors concluded that the development of such agreement and respective security policy is highly feasible, because besides the limited Russian territory in the Baltic Sea, all waters belong either to the territorial sea or the Exclusive Economic Zone (EEZ) of one of the involved States and there is not “High Seas” in the Baltics which facilitates this alternative.