The NATO-Russia relationship is undoubtedly one of the most important relationships that affects overall Euro-Atlantic security. Although, there are number of issues where NATO and Russia cooperate (ISAF mission – transit of NATO freight through the Russian territory, counter-terrorism, nuclear weapons issues, crisis management, counter-narcotics), they also face a number of challenges (missile defence in Europe, NATO enlargement), which are negatively influencing the practical cooperation and can be source of potential conflict. However, cooperation enables them to achieve important overlapping policy objectives. The goal of this paper is to analyse the challenges of NATO-Russia relations. By brief evaluation of current status of their relationship, this paper mainly specifies the future platforms of cooperation, concentrating on the post-ISAF period, as cooperation in Afghanistan is currently the most important area of NATO-Russia relations. Here, after 2014, cooperation in the present form will end which will undoubtedly bring about the search for other areas of cooperation.