What a difference the passage of five years can make! Back in 2001-02 people both in Moscow and Washington were talking about a U.S.-Russia strategic partnership, even an alliance. "Russia and the United States have common interests that ought to lead to common endeavors. This is not just talk", one astute observer of the U.S.-Russia relationship wrote in these pages back then. These days, however, no one speaks of a possible alliance; few even mention shared interests and the talk of the day is more about a new cold war than about "common endeavors." The tough attack directed by Vice President Richard Cheney against Russia in his spring 2006 speech in Vilnius and Vladimir Putin's speech at the Munich Security Conference this past February testify to how the war of words is heating up. This dramatic evolution can only lead one to ask the question: What happened? How did we move from celebrating the start of a new U.S.-Russia strategic partnership to being on the verge of a new political confrontation?

ONE EPISODE, one not particularly well-known in U.S. circles, helps to explain the downward spiral of the U.S.-Russia relationship.

October 26, 2003. Midnight. Tomorrow, early in the morning, Vladimir Putin will board his presidential plane and travel to Kishinev, the capital of Moldova. There he plans to sign a ground-breaking agreement with Moldova's president, Vladimir Voronin-the so-called "Kozak memorandum." This document is intended to bring to an end the twelve-year standoff between Moldova and Transdniestria, the self-proclaimed republic on the Moldovan border with Ukraine, populated mainly by ethnic Russians and Ukrainians. In spring 2003 Putin had named Dmitri Kozak-at that time the deputy head of his presidential administration-as his special envoy to Moldova. Kozak had a clear mandate: to find a solution to the frozen conflict that had emerged in 1993 after a short war between the central government and the separatist region. The Kozak memorandum that resulted from the negotiations offered a real prospect for a peaceful solution by turning Moldova into a federation, with Transdniestria reconstituted as a republic within Moldova-and also by guaranteeing the official status of the Russian language. Although nationalist Moldovan parties were scandalized by such a prospect, the overall agreement seemed quite reasonable, as it guaranteed the territorial integrity of Moldova and brought an end to a long-term and bloody dispute.

But closer to midnight Putin received a call from Voronin. He told him he now declined to sign the document. A startled Putin canceled the trip to Kishinev. The next day Moscow found out the reason for the abrupt change in Voronin's position.

As the story goes in Moscow, Voronin came under strong pressure from Javier Solana, the EU foreign-policy commissar, not to sign the deal. According to other sources, Voronin allegedly also had a phone conversation with Colin Powell, then the U.S. secretary of state. The message was clear: The West would not be happy if Voronoin signed the Kozak memorandum. Later, U.S. diplomats denied that there had ever been a conversation between Voronin and Powell. Nonetheless, the U.S. ambassador in Moscow, Alexander Vershbow, did confirm to me that Washington had opposed Voronin's signing the document.

Putin took U.S. involvement as a personal affront. It was seen as proof that the United States was trying to weaken Russia's influence in the post-Soviet space and that, even as Washington wanted Russian help in the context of the War on Terror, it was unprepared to be attentive to Russian concerns. It was even less understandable that at the center of the argument was the fate of 400,000 Russians and Ukrainians in Transdniestria, a region 99 percent of Americans had never heard of. To be sure, by October 2003 contradictions between Moscow and Washington on a number of issues were already tearing at the Putin-Bush partnership, and this episode was not an exception. However, this whole affair seemed to be a sort of a watershed moment when Putin started to seriously reconsider his earlier approach to the U.S.-Russian partnership.

THERE WERE strong reasons to believe initially that Putin took the idea of pursuing a strategic partnership with the United States very seriously. Yes, the man George W. Bush met in the capital of Slovenia had been a former kgb officer, but he was first and foremost a pragmatic realist. He was also absolutely willing to put aside all the mutual accusations that had accumulated between Washington and Moscow in the last years of the Clinton Administration. He hoped to start the relationship with Bush from a clean sheet of paper.

Putin took considerable political risks in offering full-fledged support to the United States after 9/11. In late September 2001 he had convened a meeting in the Kremlin with two dozen leading Russian politicians, and only two of them were in favor of supporting America in its War on Terror, while the rest felt that it was America's war and America's problem, and Russia should not get involved. Putin rejected that advice. Not only did Russia facilitate the creation of U.S. bases in Central Asia-no small favor given Russian influence in the region-but it permitted overflights of Russian territory by U.S. military aircraft and, reportedly, authorized the United States to ship equipment overland from Vladivostok to the new bases. Russia used its position with the Northern Alliance in Afghanistan to encourage close cooperation with U.S. forces. Besides, Putin gave orders to Russia's security services to share vital information with their U.S. counterparts on terrorists and radical Islamists.

Putin demonstrated he was also willing to part with the Cold War legacy and accommodate other U.S. priorities. By November 2001, the intelligence-gathering facility at Lourdes, Cuba-capable of monitoring up to 70 percent of U.S. territory-was shut down. Most notably, despite his persistent objections to the idea of the United States pursuing a national missile-defense system, Putin did not make an issue of Washington's withdrawal from the ABM Treaty.

What Putin was hoping for was a tacit agreement that, in turn, the United States would not encroach on those of Russia's priorities that did not have a major importance to America. But what he has discovered is that U.S. priorities are everywhere, even in the most unlikely areas. Let's go back to Moldova. The strategic importance of this tiny country for the United States remains a mystery for Russian observers. Yet, the desire of the Bush Administration to thwart Putin's policy towards Moldova was telling. This episode was just one in a long list of mounting grievances with the Bush Administration: the unlimited expansion of NATO; the inability to see the Jackson-Vanik amendment repealed; double standards on Chechnya; reflexive support for anti-Russian leaders on Russia's borders; no true sharing of intelligence-take your pick. Over time, it became much more difficult for Putin to claim this was a true partnership when Russia felt that Washington was only paying lip service to Russian interests, while stubbornly pursuing its own agenda-no matter how destructive it was to the partnership with Russia.

NOWHERE HAS it been seen more clearly than in Russia's relations with NATO. From 1989-91, I served as a counselor in the International Department of the Communist Party's Central Committee and was a member of Gorbachev's team of foreign-policy speechwriters and analysts. Many of us thought the way forward as the Cold War ended would be the emergence of a new Europe, one not defined by blocs, and where the old confrontations and antagonisms would be gone. Perhaps these expectations were naive, but, nonetheless, they were very appealing. In the beginning of the 1990s, the idea of a close partnership with the United States, even an alliance, was popular in Moscow. Although the Cold War ended in the fall of the Warsaw Pact and the collapse of the Soviet Union, the new Russian elites were operating from the presumption that democratic Russia should not be treated as a defeated country. On the contrary, we thought, it should be included in the Western community as a new state that had decidedly parted with communism. The thundering applause and standing ovations Boris Yeltsin received at the joint session of the two houses of the U.S. Congress in June 1992, during his first trip to the United States in his capacity as president of a democratic Russia, seemed to confirm those anticipations.

Unfortunately, the whole history of Russia's relations with NATO was a history of broken promises, guarantees and obligations. In March 1999, NATO broke its obligation to coordinate its actions with Russia when it decided to attack Yugoslavia against opposition from Moscow. It was in clear breach of the Russia-NATO Founding Act, signed on May 28, 1997, in Paris. In this act, NATO also gave a guarantee that on the territory of the new member states of the alliance there would be no military bases, troop deployments and nuclear armaments. Thus, when in December 2006 it became known that the United States plans to establish a military missile-defense base in Poland and a radar station in the Czech Republic, it was taken as yet another sign of broken obligations by the United States and its allies in Moscow. Those missile defenses might be indeed aimed at neutralizing Iran, but given that NATO in the past had broken its obligations, Putin had reasons to worry they were but the first steps in a system that in the future would be aimed at Russia's nuclear potential. All the more so that by mid-March it transpired that the U.S. administration plans to establish such radar stations in Ukraine, Georgia and Azerbaijan as well.