On 1 May 2004, the European Union (EU) welcomed eight states from the so called “Eastern Bloc”, namely the Czech Republic, Estonia, Hungary, Latvia, Lithuania, Poland, Slovakia and Slovenia. With this enlargement the EU accepted countries that have different historical, political and –in some aspects– cultural identity. While the underlying values of human rights, the rule of law and democracy should have been the catalyst for the democratic transformation of many of these Member States, their historical identities and ‘understanding’ of the democratic values have been preventing successful integration and the birth of ‘The European’ identity. For many, this is associated, rightly or wrongly, with these Member States’ struggle between their national interests and ‘EU interest’, both at the national and the international level. For instance, the current migration crisis in Europe and the failure of solidarity policy on the part of Hungarian government well represent the impact of ‘memory politics’. In this context, this paper examines how and why the historical memories, narratives and identities cause a gap between the “old” and “new” Member States. It will further look at how diverging interpretations of the Soviet past and concomitant debates on recognition have given rise to a split in the EU identity both at the national and international levels, and at how these interpretations shape the conception of European identity. Finally, this article will seek for new ways that can trace patterns toward a construction of a common ‘European identity’.