The South Caucasus is one of the most important geostrategic regions between Europe and Asia, a playground for many regional and global actors with enduring interests. These interests have been clashing through the centuries. Each actor endeavors to impose its rules and tries to capitalize on the geostrategic benefits of the region. This article analyzes the main aspects, challenges, and prospects of cooperation between the countries in the South Caucasus and Russia and NATO. The authors describe the competition for power and influence in the region, the “Old Great Game,” the regional state of affairs, and possible effects of the Russian factor on the South Caucasus-NATO cooperation. They illustrate Russia’s security interests in the South Caucasus vis-à-vis NATO’s enlargement policy, outline the reasons for the Alliance’s reluctance to engage in the region actively, and current and future prospects of South Caucasus-NATO cooperation. NATO’s presence is said to counterbalance the Russian military presence in the region, but how is this managed without antagonizing the incumbent government in Moscow and what is its contribution to resolving the so-called “frozen conflicts” in order to maintain the security and prosperity of the South Caucasus? The combination of competition and confrontation has been designated as the “New Great Game,” with clear similarities and differences vis-à-vis the “Old Great Game.” The authors question whether a “New Great Game” currently exists and apply comparative analysis, synthesis, inductive, and deductive methods to come up with conclusive answers.