One decade after the definite end of the Cold War division of the European continent, a new regional system has yet to be developed. In this context, EU-Russia relations undoubtedly play a crucial role. They are marked by challenges on and for both sides, which stem from ongoing restructuring processes in economic, political and societal spheres. Trying to adjust to the requirements of a globalising world and seeking to strengthen their role in world politics, the EU member states have initiated processes of institutional deepening and geographical widening of the Union, which are interwoven but nonetheless replete with contradictions. Projects such as the completion of the common market or the CFSP demand a high degree of internal economic and political homogeneity, whereas the accession of post-communist states will inevitably foster heterogeneity in an enlarged Union. Consequently the question of how far eastward the EU is able and willing to extend its borders becomes evident. Russia's foreign policy - facing the hardships of the transition period and the threat of finding itself on the periphery of different regionalisation processes on the global level - has been oscillating between a strategy of either becoming at least somehow connected to an enlarged Western Europe or creating its own integration space in Eastern Europe. Against this background Moscow has also been forced to reactivate relations with former Soviet republics and even CMEA partners. The article seeks to show that EU-Russia interaction in the crucial fields of security policy, trade relations and visa policy is leading to the emergence of a semi-permeable border dividing the "Ins" and "Outs" of EU-enlargement. Thus special emphasis is given to the role of the Central and East European states as possible future subjects of EU policy-making and objects of Russian foreign policy.