This paper investigates the relationship between immigration and the size of the informal or underground economy. Exploiting the variation across 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 province generates between a 3 and 8 percentage pointsincrease in unregistered employment. We also find that the controversial regularization of illegal aliensconducted in 2005 substantially reduced the number of illegal workers but did not affect the relationshipbetween immigration and informality. In contrast, we do find that this relationship becomes stronger during the economic recession inaugurated in 2008.