Low rates of internal migration in many European countries contribute to the persistence of significant regional labor market differences. To further our understanding of the underlying reasons I study internal migration in Germany, using the Mikrozensus, a very large sample of households living in Germany. The first contribution of this paper is to quantify the low mobility of the German population by estimating the unobserved cost of migration. I then focus on the differences between immigrants and natives, and start by presenting reduced-form econometric evidence for the hypothesis that immigrants, once they are in the country of destination, are more mobile than natives. Observable, individual-level characteristics can only explain part of this finding. To estimate differences in the responsiveness to labor market characteristics that are due to unobserved characteristics, I then estimate conditional logit models of the migration decision across the German federal states. I find significantly higher responsiveness to labor market differentials in the immigrant population than in the native population. Unobserved moving costs for immigrants are estimated to be only about 37% of this same cost for natives. The findings bear on the assessment of the economic impact of immigration, and the paper contributes to the current immigration-related policy debates that feature prominently in many European countries, and that likely will continue to be important in light of the ongoing EU expansion and the expected resulting east-west migration.