In the era of its state independence, Ukraine, which was previously closed to the rest of the world, became an arena for the migration flows of different nature and direction. The state admitted repatriates including those who were earlier deported by the Soviet totalitarian regime and provided asylum for refuges. As a result of abrupt economic decline, international labor migration of Ukrainian citizens scaled up. Illegal migration has dual effect on Ukraine. On one hand, Ukraine is a country of origin for hundred thousands labor migrants working in Russia and EU states without appropriate documents. On the other hand, significant number of foreigners entries Ukraine breaching border crossing and residence regulations, most of them expect to transit through the state’s territory further to the West. Strengthening the state borders as well as visa and migration control restrained the illegal migration flows from Asia and Africa, increased the number of potential illegal migrants disallowed entering the country, and affected the national structure of the illegal migration with the growing number of migrants from the post-Soviet states which still have non-visa regime with Ukraine. At the same time, illegal migration remains to be a serious challenge for Ukraine. It has become for Ukraine an outstanding factor in the international relations with its neighbor in the West as well as in the East. It’s closely associated with shadow economy and corruption. Imperfections of the national asylum granting system became very visible in the context of illegal migration. Human rights organizations and law-enforcement agencies record the growing intolerance of the population and increasing number of nationnality or race associated cases of violence linked to the phenomenon. All of these detects the importance of the prevention of illegal migration in the context of Ukraine’s national migration policy and its international relations.