In this paper we analyze the impact of immigrants on the type and quantity of native jobs. We use data on fifteen Western European countries during the 1996-2010 period. We find that immigrants, by taking manual-routine type of occupations pushed natives towards more "complex" (abstract and communication) jobs. Such positive reallocation occurred while the total number of jobs held by natives was unaffected. This job upgrade was associated in the short run to a 0.6% increase in native wages for a doubling of the immigrants' share. These results are robust to the use of two alternative IV strategies based on past settlement of immigrants across European countries measured alternatively with Census or Labor Force data. The job upgrade slowed, but did not come to a halt, during the Great Recession. We also document the labor market flows behind it: the complexity of jobs offered to new native hires was higher relative to the complexity of lost jobs. Finally, we find evidence that such reallocation was significantly larger in countries with more flexible labor laws and that his tendency was particularly strong for less educated workers.