This paper studies the legalization of 600,000 non-EU immigrants by the unexpectedly elected Spanish government following the terrorist attacks of 2004. By comparing non-EU to EU immigrants we first estimate that the policy did not lead to magnet effects. We then show that the policy change increased labor market opportunities for immigrants by allowing them to enter sectors of the economy with fewer informal employment. We rely on cross-province comparisons to document that payroll-tax revenues increased by around 4,000 euros per legalized immigrant, and the heterogeneous effect of the policy on various groups of workers. We provide a theoretical framework based on monopsonistic competition to guide our empirical work and interpret our findings.