In May 1995, it was agreed to develop, in addition, what was termed “Broad, Enhanced Dialogue and Cooperation” between NATO and Russia, on a separate, bilateral basis.

The NATO-Russia relationship was further strengthened in January 1996 when Russian forces joined NATO troops in the Implementation Force (IFOR), organised to implement the military aspects of the Peace Agreement in Bosnia-Herzegovina. Russian forces remain in Bosnia today as an important part of the NATO-led Stabilisation Force (SFOR). Since this cooperation began, both NATO and Russian forces have gained valuable, practical experience in working together. In spite of the positive development of this cooperation, the issue of NATO enlargement troubled the relationship between NATO and Russia. In response to the strong desires of new democracies in Central and Eastern Europe to join NATO, the Allies agreed in December 1994 to study “the why and how” of NATO enlargement. Most Russians viewed this and subsequent steps toward enlargement as a threat to Russian prestige, and for some it represented a threat to Russian security.

Russia’s attitude toward NATO enlargement reflected feelings about the Alliance that had been reinforced by four decades of Soviet propaganda. Many Russians found it difficult to accept that there were fundamental differences between NATO, a voluntary Alliance among independent countries, and the Warsaw Pact, where membership was imposed by the Soviet Union. The NATO Allies decided it was important to respond to the desire of the new democracies to join NATO, despite these expressions of concern and open opposition by many Russians.

At the same time they recognised the importance of trying to overcome Russian doubts and opposition by demonstrating that NATO did not represent a threat to Russia or its interests. On the contrary, it would serve the interests of the international community as a whole by creating greater stability throughout Europe. Moreover, there was a genuine respect for Russia and its position in the world and a determination to develop NATO-Russian cooperation. However, doubts over the wisdom of this policy were not limited to Russia and some Western analysts questioned the viability of this new relationship between former antagonistic powers. NATO’s efforts to reassure both Russian and other critics took several forms. The NATO Allies pledged that they had “no intention, no plan and no reason” to deploy nuclear weapons on the territory of new NATO member countries. They also said that they planned no permanent, substantial deployments of NATO soldiers in any new member states. Perhaps most importantly, the Allies authorised the NATO Secretary General to negotiate a more permanent cooperative relationship with Russia.