This paper investigates the relationship between immigration and the size of the informal or underground economy. Using regional variation for the Spanish provinces we find that the massive immigration wave between 2000 and 2009 is highly correlated to the share of unregistered employment, a proxy for the size of the underground or informal labor market. We estimate that a 10 percentage points increase in the share of immigrants in a region generates between a 3 and 8 percentage points increase in unregistered employment. We also find that the controversial regularization of illegal aliens conducted in 2005 substantially reduced the number of illegal workers but did not affect the relationship between immigration and informality.