Negative perceptions about migrants in Europe, the Continent with the largest social policy programmes, are driven by concerns that foreigners are a net fiscal burden. Paradoxically instruments of social inclusion are becoming a weapon of mass exclusion. Increasing concerns of public opinion are indeed pressing Governments, in the midst of the recession, to reduce welfare access by migrants or further tighten migration policies. Are there politically feasible alternatives to these two hardly enforceable (and procyclical) policy options? In this paper we look at economic and cultural determinants of negative perceptions about migrants in Europe. Based on a simple model of the perceived fiscal effects of migration and on a largely unexploited database (EU-Silc), we find no evidence that legal migrants, notably skilled migrants, are net recipients of transfers from the state. However, there is evidence of "residual dependency" on non-contributory transfers and self-selection of migrants more likely to draw on welfare in the countries with the most generous welfare state. Moreover, redistribution does not find much support among those who are in favour of immigration. A way out of the migration into the welfare state dilemma facing Europe involves i. co-ordinating safety nets across the EU, ii. adopting explicitly selective migration policies, and iii. improving activation programmes. Other options – such as restricting migration or welfare access by migrants – are however on the agenda of national Governments.