Background: Migrants from Eastern Europe constitute more than 5% of Germany's population. Since population health in their countries of origin is poor their health status upon arrival may be worse than that of the native-born German population (hypothesis H1). As a minority, they may be socio-economically disadvantaged (H2), and their health status may deteriorate quickly (H3). Methods: We compared data from 1995 and 2000 for immigrants from Eastern Europe (n = 353) and a random sample of age-matched Germans (n = 2, 824) from the German Socioeconomic Panel. We tested H1-3 using health satisfaction, as a proxy for health status, and socioeconomic indicators. We compared changes over time within groups, and between immigrants and Germans. We assessed effects of socio-economic status and being a migrant on declining health satisfaction in a regression model. Results: In 1995, immigrants under 55 years had a significantly higher health satisfaction than Germans. Above age 54, health satisfaction did not differ. By 2000, immigrants' health satisfaction had declined to German levels. Whereas in 1995 immigrants had a significantly lower SES, differences five years later had declined. In the regression model, immigrant status was much stronger associated with declining health satisfaction than low SES. Conclusion: In contrast to H1, younger immigrants had an initial health advantage. Immigrants were initially socio-economically disadvantaged (H2), but their SES improved over time. The decrease in health satisfaction was much steeper in immigrants and this was not associated with differences in SES (H3). Immigrants from Eastern Europe have a high risk of deteriorating health, in spite of socio-economic improvements.