This paper investigates the consequences of the legalization of around 600,000 immigrants by the unexpectedly elected Spanish government of Zapatero following the terrorist attacks of March 2004 (Garcia-Montalvo (2011)). Using detailed data from payroll-tax revenues, we estimate that each newly legalized immigrant increased social-security revenues by 3,504 Euros on average. This estimate is only 49 percent of what we would have expected from the size of the newly documented immigrants, which suggests that newly legalized immigrants probably earned lower wages than, and maybe affected the labor-market outcomes of, other workers. We estimate that the policy change deteriorated the labor-market outcomes of some low-skilled natives and immigrants and improved the outcomes of high-skilled natives and immigrants. This led some low-skilled immigrants to move away from high-immigrant locations. Correcting for migration and selection, we obtain that each newly legalized immigrant increased payroll-tax revenues by 4,398 Euros or 26 percent more than the raw payroll-tax revenue data estimates. This shows the importance of looking both at public revenue data and the labor market to understand the consequences of amnesty programs fully.