The article is devoted to the study of evolution of public perceptions of new Russia’s borders through the analysis of their representation in Russian printed media. “Nezavisimaya Gazeta” was chosen as a focus newspaper. The study is based on a database of publications collected through screening of this edition in four periods: 1994-1995, 2000-2003, 2008-2012 and 2013-2014. The newspapers “Sovetskaya Rossiya”, “Zavtra” and “Novaya Gazeta” were used as the sources of additional information. The authors discovered that modernized East-West dilemma serves as a framework of these representations. Russia faces a fundamental choice between two vectors. The Western (European) vector means the rapprochement with the EU and NATO, adoption of their values and development models. The Eastern (Eurasian) one implies total or partial reintegration of post-Soviet space and creation of new autonomous center of power within upcoming multi-polar world. Debates about the future of newly formed borders and the whole post-Soviet space, about building relations with former union republics on the one hand and the EU and NATO on the other, about aims and composition of regional integration projects etc. has invariably focused on the analysis of this dilemma. Since the 1990s there have been changes not only with the balance between two vectors within the media political discourse (non-contradicted in early 1990s they turned in the middle of 2010s into opposite sides of a dichotomy while the eastern vector appeared to be a dominant one) but also with their proper understanding. This article concerns with the Eastern part of two-faced discourse that reflects the transformation of Eurasian integration from the process of mutual attraction of Russia and other post-Soviet republics after a long period of coexistence as parts of a single state to one of the basic forms of global war between East-Russian and collective West. The issue of identity, state building and “battles of memories” which influence the perception of post-Soviet borders are considered in the same context. The final section assesses the possibility of usage of semantical approach to the analysis of meanings (words and senses) forming political language.