With the end of the Cold War the Black Sea area has seen the proliferation of international organizations while the stalemated security challenges symbolized by the three frozen conflicts remain: Moldova vs. Transniestria; Armenia vs. Azerbaijan; Georgia vs. Abkhazia and Southern Ossetia. Identifying the region as a multi-polar system the chapter explores the dynamics among the major actors as well as between the major and lesser actors. This includes conflicts, negotiations and alliances. Because of the pervading mistrust among the actors the paper concludes that a comprehensive solution to the security issues in the region would be the most likely to produce successful negotiations of the frozen conflicts.