With the enlargement of the European Union, new bordering countries emerged in the East which are characterized by comparatively low incomes and living standards, incomplete democratization and a number of latent political conflicts. Against this background it can be expected that migrations from these countries into the European Union will be growing, although a considerable part of the expected movements might be temporary or circular. Focussing on the Ukraine which shares borders with four European Union countries (Poland, Slovakia, Hungary, Romania) and which entertains migration relations with a number of European Union member states, this study identifies the new migration challenges at the Eastern borders of the enlarged European Union. The study reveals, that some European Union states are particularly addressed by Ukrainian labour migrations. Whereas high income differences and a lack of job opportunities in the home country trigger these movements in general, they are additionally based on traditional migration patterns and network relations in states such as Germany, Poland, Hungary, the Czech and the Slovak Republic. In other EU member states, such as Portugal, Spain, Italy and Greece, the demand for low-skilled labour in segmented markets, particularly in the nontraded goods sectors of the economy seems to have primarily supported the movement of Ukrainian labour migrants. Although the European Union has recently undertaken some efforts to develop common migration regulations, many of the proposed policy measurements are still indeterminate, particularly in the case of lowskilled labour movements.