Issues related to assessing the budgetary effect of labor migration have acquired particular importance due to reform of legislative framework for attracting and using foreign labor. The goal of this study is to assess the damage from illegal external labor migration for the Russian budget and suggest measures to reduce it. The following methods were used fir the study: comparative analysis, systemic and structural method, design calculations, the comparative method. The main results are presented in the form of quantitative values of personal income tax losses from labor income of migrants employed in the informal sector of the Russian economy, as well as variation trends during the review period. The novel result obtained in the study is the methodology developed for assessing tax losses based on potential and actually received personal income tax amounts from labor income of foreign citizens, instead of scale of illegal labor migration. It was concluded that illegal labor migration makes a huge contribution to the GDP of our country but at the same time causes great damage to the Russian budget. In addition, the losses of personal income tax has increased by 60% in 2017 compared to 2016, because migrants prefer to work illegally due to increased complications with obtaining patents. To solve this problem, it is necessary to simplify registration procedures (passing examinations, obtaining patents) for migrants from neighboring countries (especially from CIS countries). Certain barriers should exist, namely: health status, knowledge of the destination country’s language, but the main function of these barriers should not be restricting entry. In addition, preliminary training of workers of specific professions is necessary in their home countries. This requires intergovernmental agreements legalizing such educational activities in a particular country. Refining the methodology by including calculation of insurance premium losses due to illegal labor activities of migrants in Russian Federation seems a promising direction for further research.