In this paper the relationship between the EU labor markets and Eastern Enlargement is examined. Several issues will be examined throughout the paper, namely the current challenges and problems of the EU labor markets, their impacts on the overall competitiveness of the European economy, and the possible effects of the Eastern enlargement on both of these.