The cooperation among the Navies of the Black Sea region has a significant, and as yet underutilized potential to deal with the new security challenges. In this article the Chief of Staff of the Bulgarian Navy describes the non-traditional challenges in front of the Bulgarian Navy and other governmental agencies, and the role advanced IT may play in facilitating their effectiveness. Building on that experience, Vice-Admiral Petrov proposes a regional initiative in establishing a unified Black Sea information system. He analyzes functional, organizational and technological aspects of the project, defines priorities in its development and proposes initial implementation steps.