This paper assesses how new immigrants to Spain fare in the country's labor market, evaluating the conditions under which they are able to find employment, and their progress out of unskilled work into middle-skilled jobs. Using Spanish Labor Force Survey data from 2000 through 2011, we find that immigrants who arrived before the 2008 recession had little trouble finding work immediately, but those who arrived after 2008 struggled to find work as Spanish unemployment rates skyrocketed. Immigrants' individual characteristics had a limited effect on their employment trajectories. Although many immigrants who arrived in Spain between 2000 and 2007 were able to find work and eventually move out of the low-skilled positions, the nature of their jobs meant that they were not protected from the recession, and many became unemployed as the economy shed low- and middle-skilled jobs in sectors dominated by immigrants. In the long term, Spain will likely need immigrants to cover labor shortages because of its aging population and the emigration of native-born workers to other countries. The findings suggest that for many workers, finding middle-skilled work alone isn't enough, and integration policies could aim to help workers transition from the secondary to the primary labor market in order to find their way into more stable employment.