The concept of “Eastern Europe” was always ideologically, politically, strategically or even culturally defined, while pure geography was down on the list of criteria. We therefore consider Eastern Europe a geopolitical idea on a dynamic mental map rather than a geographic reality. In the past three decades, Eastern Europe had at least three meanings, from the former “socialist bloc”, then “East Central European post-communist countries”, to the present member states of the “EU’s Eastern Neighbourhood” or Eastern Partnership (EaP). None of the countries of the pre-1989 Eastern Europe is still in this category, all being “transferred” to Central Europe, while the “new Eastern Europe” currently consists of six post-Soviet republics, from Belarus in the north to Azerbaijan in the south. This paper analyses the geopolitical context of the new Eastern Europe after the launch of the EaP, focusing on Ukraine and the Republic of Moldova, caught between the crisis of the EU, their own vulnerabilities and a more threatening Russian Federation.