NATO Secretary General Anders Fogh Rasmussen has made ties with Moscow a priority since he took office in August.
His first visit to Moscow, from Tuesday to Thursday, is seen as the most recent effort to rebuild a relationship that was strained in the wake of the Caucasus war in August 2008.
Though Moscow gave no immediate promise of greater assistance for the western military alliance's operation in Afghanistan, the former Cold War foes have both expressed willingness to enhance security cooperation despite lingering differences.
Thaw in ties
Russia-NATO relations sunk to a Cold War-style chill following last year's brief war between Russia and Georgia, a former Soviet republic that has allied itself with the United States.
But ties between NATO and Moscow have improved significantly in recent months. In a sign that their relations have returned to the pre-conflict level, Russia and NATO resumed contacts within the Russia-NATO Council early this month.
Rasmussen said on Wednesday at a meeting with Russian President Dmitry Medvedev that NATO hoped to establish a "real strategic partnership" with Russia.
Rasmussen admitted to disagreements in NATO-Russia relations, but said they should not overshadow their common interests in many fields.
Medvedev agreed that Russia and NATO should cooperate more closely, due to a rise in threats.
"We have many reasons for interaction, many subjects for discussion," including joint actions to counter terrorism, crime and other common threats, Medvedev said.
Rasmussen also held talks with Russian Prime Minister Vladimir Putin, who said he hoped for less contradictions between Russia and NATO in the future.
"A unification of Russian and NATO efforts in spheres of common interests may yield good results," Putin said.
Russia and NATO hold different views on various issues, but they continue to cooperate in the fight against terrorism, the spread of weapons of mass destruction, drug trafficking and organized crime, the premier noted.
Russia is pursuing a pragmatic foreign policy, which envisions no confrontation but cooperation, in a bid to build a good external environment for domestic development amid the global economic downturn, observers say. That's why Russia responded instantly when NATO extended an olive branch.
Cooperation on Afghanistan
During U.S President Barack Obama's visit to Moscow in July, Russia and the United States penned a deal on sending U.S. troops and military equipment to Afghanistan via flights through Russian airspace, saving the United States a huge amount of time and money.
It seems that NATO is determined to follow suit by asking Russia to back its Afghan campaign.
Speaking to reporters after the talks with Medvedev, Rasmussen said he had presented Russian leaders with a list of "concrete proposals" on rendering NATO more assistance in Afghanistan.
"I have invited Russia to step up its terms of cooperation in Afghanistan," the Danish NATO chief said, adding that Russia could contribute by supplying helicopters, spare parts and fuel, and by training pilots.
Rasmussen said Russia's cooperation in NATO's war effort in Afghanistan was beneficial to both sides. "I do believe that it's essential for Russia that we succeed in Afghanistan," he said.
"If Afghanistan once again becomes a safe haven for terrorists, then Russia would be among the first victims, as terrorists could easily spread from Afghanistan through Central Asia to Russia," Rasmussen said.
Russian Foreign Minister Sergei Lavrov, who also met with Rasmussen on Wednesday, said the president had instructed the government to study the NATO chief's proposals.
Rasmussen is reported to be seeking a broader arrangement that allows NATO to transport non-lethal supplies by railroad across Russia to Afghanistan, but he dismissed the speculation in an interview with the Ekho Moskvy radio station late Wednesday.
NATO had not asked for Moscow's permission to use its territory for the overland transit of military supplies to Afghanistan, he said. "However, NATO is interested in expanding cooperation with Russia on Afghanistan, including the transit of the alliance's cargoes."
The Taliban was likely to stage a comeback if NATO withdraws its troops from Afghanistan, said Alexei Arabatov, head of the International Security Center at the Institute for World Economy and International Relations. In that case, an Afghanistan out of control would pose a threat to Russia's national security. Russia could supply weapons to Afghanistan with compensation for security reasons, Arabatov said.
Pavel Zolotarev, deputy head of the Institute of U.S. and Canadian Studies, said Russia should place some limits on its efforts to help NATO in Afghanistan to ensure that Russia would not be in the front line of the Afghan war once U.S. troops left the war-torn country. Meanwhile, NATO should suspend its eastward expansion in return.
Disputes remain
At Wednesday's Kremlin meeting, the Russian president missed no opportunity to urge NATO to mull over Russia's proposal to create new European security mechanisms.
Medvedev in late November sent a draft treaty on European security to leaders of other countries and international organizations of the Euro-Atlantic space. But the initiative has so far received a lukewarm response from the West.
Top diplomats from NATO member states and Russia discussed the draft treaty at a meeting of the NATO-Russia Council in Geneva early December at Russia's insistence.
Rasmussen told a press conference on Thursday that a new European security treaty was unnecessary. "A lot of documents already exist in this field, so I did not see the need for signing a new one," he said.
On NATO's eastward enlargement, Rasmussen did not change his stance either. The decision to eventually absorb Georgia and Ukraine into the alliance was still in effect, he said, adding that the two countries had the right to decide on their entry into the bloc.
The NATO chief acknowledged that Russia and NATO remained at adds over the independence of Abkhazia and South Ossetia, two Georgian breakaway regions, and demanded that Russia withdraw its troops there.
Analysts believe Russia's proposal of a new European security treaty is intended to prevent NATO from expanding eastward, restructure the current NATO-led European security architecture and boost its influence as a world power.
Russia is willing to reinforce security cooperation with NATO, but NATO is opposed to any changes in the European security mechanisms. Therefore, the depth of their cooperation will depend on to what extent they can bridge major differences.
Given NATO's coldness on the new European security treaty and the continuation of eastward expansion, the prospects of their cooperation could hardly be inspiring, analysts say.
Russia-NATO relation have experienced ups and downs in the post-Cold War era. They need each other on major global and regional issues, yet they keep restraining each other due to many differences. The future of Russia-NATO ties hinges on whether they can settle these long-existing disputes, analysts say.