The end of the 20th century was marked by a rather unexpected opening as the long-enduring Cold War came to the end and the Soviet Union collapsed, allowing fifteen new republics to appear on the political scene. Beyond the optimistic expectations of democratization and the expansion of free-market capitalism through the newly independent republics, the collapse of the Soviet Union created serious challenges for the international community in terms of international law, politics, economy, and security. One problematic challenge, which remains an open issue today, is the painful process of disintegration of the multi-ethnic Soviet federal state. By evaluating the current state of affairs of the non-NATO member, Kremlin disloyal post-Soviet states located on the western frontier of the Russian Federation, we can see that they have become a “bone of contention” between the West and Russia. By presenting brand new evidence from the Gorbachev period, once top-secret meetings of the CPSU Politburo and other Soviet governmental institutions, this article critically evaluates issues such as Gorbachev’s grand compromises in Central and Eastern Europe and the Russian problem in Ukraine and probable risks of its further aggravation, and tries to draw recommendations for solving current territorial problems in the region.