This paper analyses the dynamics of the unemployment rate in the eight countries from Central and Eastern Europe which joined the EU in 2004. Unit root tests allowing for nonlinearities and structural changes suggest that the unemployment rate is not stationary in most of the sample countries. Tests allowing for fractional integration, however, reveal that shocks are highly persistent, implying a slow rate of convergence to the natural rate of unemployment. The unemployment rate is least persistent in Hungary and Slovenia, more persistent in the Czech Republic, Slovakia and the Baltic States and extremely persistent in Poland. The degree of persistence appears to reflect the different levels of economic and institutional development in the countries and possibly also the role of the government.