NATO-Russia relations today are characterized by a paradox: On the one hand, there is an enormous security agenda waiting to be tackled by us together - from nuclear security to combating international terrorism. Yet, on the other hand, we have not yet been able to exploit our cooperative potential in these areas. Because there is still a tendency to concentrate on our differences. Why is this so?

Part of the answer is that, even 10 years after the end of the ideological and military confrontation in Europe, we still cling to old stereotypes. These stereotypes come to the fore whenever our interests or perceptions diverge. Kosovo is the most obvious case in point.

For NATO Allies and a large part of the international community, the Kosovo campaign was a struggle to avert a humanitarian tragedy, to prevent a destabilization of the wider region and to uphold key values on which the Europe of the 21st century should be built.

Many Russians, by contrast, seemed to view NATO's actions as a geopolitical plot to establish a permanent NATO presence in the Balkans. Russia also criticized NATO for having acted without a specific U.N. resolution, whereas NATO argued that it was acting in the spirit of the United Nations Charter and that a resolution was unachievable precisely because of the known Russian reservations in the UN Security Council. In short, while Russia accused the West of acting unilaterally, the Western view was that it was in fact Russia who appeared reluctant to share the responsibility of stopping another Balkan tragedy from unfolding.

Let me be clear: To have different views on something as important as Kosovo is to be expected. Even NATO Allies did not always see eye to eye on how to deal with such a complex challenge. But we were able to iron out our internal differences through open dialogue. To Allies, Russia's reaction seemed to reflect an underlying feeling that NATO's views were motivated by a deliberate anti-Russian design and disregard for Russian interests. Eventually, our consultations in the NATO-Russia Permanent Joint Council fell victim to this perception: Although we had many frank and highly useful discussions during the unfolding Kosovo crisis, Russia decided to suspend them once NATO's air campaign began. Now they have resumed - but are, for the time being, restricted to Balkan issues only.

I do not want to imply that our disagreements are simply "misunderstandings." Some of our differences are both real and significant. What I take issue with, however, is the way we cope with such dissent. We cannot allow disagreement to jeopardize the entire range of NATO-Russia relations, as if these relations were some kind of dispensable luxury. NATO and Russia are two major players in European security. A permanent strategic dialogue is in our mutual interest, as it is in the interest of virtually everybody else.

For several years, NATO and Russia have acted in accordance with this logic. Piercing the veil of mistrust left from Cold War days, we made progress previously thought unachievable. The signing of the NATO-Russia Founding Act in May 1997 and the creation of the NATO-Russia Permanent Joint Council were a watershed in European security. From now on, NATO and Russia would no longer consider each other as adversaries. From now on, we would consult on the key issues affecting our mutual security. From now on, security would no longer be a zero-sum game, where one's gain is the other's loss.

Our Work Program reflected this new spirit of cooperative security. It covered a host of issues that we needed to tackle together: preventing the proliferation of weapons of mass destruction, retraining of military personnel, cooperation in science and environmental issues, or armaments cooperation. The possibility of setting up of a NATO Information Office in Moscow was foreseen, and a Military Liaison Mission in Moscow was about to be established. None of these initiatives was bound to change history overnight. But we believed that, if fully and steadily implemented, they had the potential to achieve something revolutionary: to turn former adversaries into partners and even friends.

NATO and Russia were able to make this much progress because together we opted for pragmatism, not ideology. In the determination to live up to our shared responsibility, NATO and Russia acted according to their strategic interests, not according to historical reflexes. We saw a historic chance and seized it. Indeed, by the time we signed the Founding Act, realities on the ground were already pushing us more and more towards cooperation: Soldiers from NATO, Partner countries and Russia were already successfully cooperating in Bosnia. And Russian officers were already working at NATO's military headquarters in Belgium to facilitate our military cooperation in Bosnia. Hence, a more structured NATO-Russia political relationship was both logical and inevitable. In essence, it was an acknowledgement of a powerful political reality: that we are destined to cooperate.

In fact, even in Kosovo, these powerful political dynamics prevailed once again and pulled us toward cooperation. Although we did not always share the same perspective, the West and Russia developed a common diplomatic approach to end the crisis and are now on the ground together pushing the region towards a sustainable peace. Even if our common goal of a peaceful Kosovo within a democratic Yugoslavia requires years of hard work, there can be no doubt that NATO and Russia can achieve it if we collectively keep our eye on the ball.

Clearly, our cooperation in the Balkans will have a defining impact on the future of NATO-Russia relations. But why limit our discussions to Kosovo only? Didn't Kosovo reveal that our relationship suffers from too little, not too much dialogue?

I am convinced: European security does not stand to gain from self-imposed silence. We need the broadest possible dialogue - both in the Permanent Joint Council and in other fora. We have plenty of issues to discuss. Consider, for example, the new Russian draft military doctrine. We are concerned that the draft moves away from the principle of cooperative security, as its paints a darker, more confrontational picture of international relations.

Chechnya, too, is a point of common concern. Clearly, every sovereign state has a right - and a duty - to combat terrorism. But we should never stop asking: Does the end really justify the means being applied? Beyond serious humanitarian concerns, the conflict also raises other questions. With Russian military deployments in the Caucasus being in excess of current and planned limits set by the Treaty on Conventional Forces in Europe, the conflict risks undermining the success of the Istanbul OSCE Summit later this month. Both Russia and the West have placed high hopes in this summit as a means to clear the obstacles on the road toward renewed NATO-Russia cooperation. We must not let it fail.

All this leads me to one clear-cut conclusion. We must get the NATO-Russia relationship out of its artificial straitjacket. We must release our dialogue from its self-imposed limitations. Disagreements are a reason to talk more, not less. Ten years after the end of the Cold War, at the dawn of the 21st century, the NATO-Russia relationship must evolve into a true strategic partnership. Let's get back to business.