The article investigates the evolution of the Russian-Kazakhstani relations at the second stage of the post-Crimea period (August 2016 – March 2019). Based on a wide range of official sources and periodicals, it identifies the main trends and issues of bilateral cooperation in the political, economic, and humanitarian spheres, as well as at the interregional level. It determines the main factors that influenced the interaction between Moscow and Astana. It pays particular attention to the role of the presidents of Russia and Kazakhstan in promoting and strengthening their alliance and strategic partnership. It concludes that the period under consideration was a time for relative stabilization of Russian-Kazakhstani relations, which replaced the powerful turbulence that emerged in the context of the events of the “Ukrainian crisis” and “Crimean Spring”. However, despite the significant results achieved by the parties during the period, they failed to solve their most important challenge, which was the excessive dependence of the system of their interaction on the foreign policy preferences of Russia and Kazakhstan’s national leaders. As a result, the active development of the bilateral cooperation was ensured not so much by objective reasons as by the support provided to the process by Presidents Vladimir Putin and Nursultan Nazarbayev. Therefore, Nazarbayev’s resignation as head of state could result in unpredictable consequences for Russia-Kazakhstan relations.