Since the independence, Moldova’s leadership have been divided between those who pledged for withdrawal from the CIS, as a pre-condition to Moldova’s European Integration, and those in favour of preserving closer links with the Soviet space. Leaders of the new state embraced the idea of compatibility between Moldova’s simultaneous integration within Eastern and Western systems, with the EU turning upside down this assumption, and indicating that Moldova will have to choose between the two, in the case of a deeper European integration. The paper will examine how Moldova’s European discourse developed in the first decade of its independence and what role was played by the double-faced foreign policy in slowing Moldova down on its journey “back to Europe”. My hypothesis is that concomitant integration into the CIS and the EU is a contradiction in terms given the different set of values of the two. Having joined the CIS, Moldova has drastically limited its possibilities to participate in EU’s political and economic policies, as well as in its institutions, remaining a satellite of Moscow’s orbit. If serious about integration into the EU, Moldova will have to quit the CIS, with Romania, as EU member, having the potential to serve as a locomotive for Moldova on its journey "back to Europe".