Secure and well-managed migration and mobility figure prominently in the European Union’s (EU) relations with its Eastern neighbors. In the framework of the European Neighborhood Policy (ENP) and the Eastern Partnership (EaP), the EU relies extensively on policy conditionality as it ties the reward of visa-free travel to the adoption of specific policies by neighboring countries in order to better regulate and manage mobility and migration. However, in the post-Soviet space migration flows and management are, to a great extent, still shaped by (post-) Soviet legacies and interdependences. As a result, Russian domestic and foreign policies shape the way migration and mobility are perceived and managed by neighborhood countries. In this article, we seek to investigate what effect these historically-grown ties and current foreign policy actions exert on compliance with EU requirements for visa liberalization in Armenia, Georgia and Moldova. In all three countries, we identify patterns of change over time and explain them according to the interplay of partner countries’ political preferences with EU policy conditionality and incentives by Russia.