This paper takes its interest in understanding the impact of the influx of non-EU immigrants into the EU on the creation of new shared narratives of European integration and nationalism. In particular, the paper analyses how language is used by political actors on the European, national (Belgian) and regional (Flemish) level to promote European integrationist or nationalist agendas by framing the ‘problem’ of immigration and integration accordingly. To analyze the discursive process by which narratives become established in the social context of immigration, the paper undertakes a Critical Discourse Analysis of policy documents and media reports, in which discursive elements of political language are discussed in relation to the wider socio-political environment. By analyzing the immigration discourse at different levels of European governance (EU, national, regional), the paper shows how the discourse on immigration in Belgium has led to the seemingly paradoxical situation of strengthening both the narrative of European integration as well as that of Flemish nationalism.