The second time around wasn't so tough either. To be sure, Moscow objected boisterously when the Western alliance expanded into the post-Soviet space in 2004, admitting Estonia, Latvia, and Lithuania, in addition to Bulgaria, Romania, Slovenia, and Slovakia. But in the end, it could do little to stop the move.
But then the enlargement wave hit a brick wall. When NATO began moving to admit Georgia and Ukraine, a newly emboldened Russia effectively drew the line.
Flush with petrodollars and newfound influence, the Kremlin brought all its political, economic, and diplomatic strength to bear at the alliance's 2008 summit in Bucharest.
Tbilisi and Kyiv had come to the Romanian capital with hopes of taking a key step forward in their NATO bids. Instead, they left empty-handed, as Moscow appeared to shut down the next wave of expansion before it even got off the ground.
Today, prospects for Georgia and Ukraine seem even more dim despite U.S. Secretary of State Hillary Clinton's assurance on April 3 that the process is "moving on."
"I don't see any reason why Georgia and Ukraine cannot join NATO when the time is right -- when they have good relations with their neighbors," Edgar Buckley, the former NATO assistant secretary-general for defense planning, said at a recent conference in Prague. "We don't want to take Georgia into NATO so that we can have a war with Russia. No thanks, is what I say to that."
As NATO heads of state gather in France and Germany for their summit marking the trans-Atlantic alliance's 60th anniversary, it will be with a creeping sense that enlargement -- particularly into the territory of the former Soviet Union -- may have reached its limits.
A military alliance that has expanded from 16 to 28 members since the fall of the Berlin Wall, and once appeared poised to stretch from North America to the Caucasus, suddenly finds itself in an insular mood.
It's not only Georgia and Ukraine whose bids are off the table for the time being. Macedonia's long-standing application has also been put on hold, due to an ongoing dispute with NATO member Greece.
"Europe has effectively closed its doors to Georgia and Ukraine. This is not good," says Bruce Jackson, a U.S. expert who heads the Washington-based Project on Transitional Democracies. "The defining purpose of NATO since the early 1990s has been the expansion of NATO. This has been arrested in the Balkans and has collapsed completely in the East."
Russia's resurgence, and its increased ability to sow discord among the allies, accounts for a great deal of NATO's stalled enlargement -- but not all of it. There are deep philosophical divisions within the alliance over expansion, with the United States, Britain, and most new members supporting expansion, as Germany, France, and Italy have become increasingly opposed.
Moreover, there is a growing sense that new aspirants like Georgia and Ukraine simply do not meet the political and military requirements for membership. Clinton acknowledged those concerns ahead of this week's summit, saying those countries must meet the alliance's standards in order to join.
"Within Europe there was a much more solid anti-expansion camp than we've seen before," says Edward Lucas, a correspondent for the British weekly "The Economist" and author of the book "The New Cold War."
"In the previous round of expansion [in 2004], Germany was quite reluctant. In the end, Germany went along with it because everybody else was going along. The pro-expansion people were able to build a very effective coalition within NATO. This time around, the anti-expansion camp was much stronger."
Critics have alleged that Germany's stance is unduly influenced by its extensive business ties with Moscow, particularly in the energy sector.
Indeed, analysts say the divisions among the allies over expansion reflect sharp disagreements over the level of threat posed by Russia.
"We're in a rather paradoxical situation. Russia is enough of a problem that NATO needs to do more. But Russia is not enough of a problem to concentrate NATO's minds. So that's why we get this rather inadequate response," Lucas says.
With the administration of U.S. President Barack Obama seeking a "reset" in relations with Moscow, it seems likely that the softer Franco-German position will be ascendant, at least in the short term. The alliance this month agreed to restore normal ties with Russia, which were suspended in the wake of the war with Georgia in August.
This lack of cohesion on Russia, analysts say, threatens to undermine NATO's military effectiveness.
"We believed that NATO could function effectively without a consensus on Russia. But the divisions...that have been allowed to go unresolved...have been the single largest factor in the breakdown of organizational effectiveness," Jackson says. "Military organizations do not handle ambiguity well."
Out Of Area
Despite the mood of retrenchment, NATO enlargement is not off the table entirely. Albania and Croatia received invitations to join the alliance in Bucharest and on April 1 became NATO's 27th and 28th members. There is increasing talk of Sweden and Finland -- both of whom were neutral in the Cold War -- joining in the future.
But by all appearances, expansion into the ex-USSR is indefinitely on hold. Even so, Russia claims it is the aggrieved party in its dealings with NATO.
Moscow says, for example, that when East and West Germany reunited as a NATO country in 1990, the Kremlin received assurances from the United States that NATO would not expand farther East. U.S. officials, however, deny making such a pledge.
Moscow also pushed for -- but did not receive -- assurances from Washington when the Czechs, Poles, and Hungarians joined in 1999 that no military bases would be installed in these countries.
As fanciful as it sounds today, in the heady days after the Soviet collapse, there was even high-level talk of considering a NATO bid by Russia itself. In late 1991, then Russian President Boris Yeltsin stunned NATO officials by saying joining NATO was a "long-term political objective" for Moscow. The alliance, however, never took the proposal seriously.
Jamie Shea, director of policy planning in the NATO secretary-general's office, tells RFE/RL that despite the current hand-wringing, this has led to a more stable Europe.
"The end of the Cold War brought about a situation where NATO discovered a new role for itself in terms of defense reform and security-sector reform, helping these former communist countries to get back on their feet," Shea says. "Enlarging NATO was not just to get bigger -- because there is no point in enlarging just to get bigger -- but more importantly, to expand the zone of peace and stability in Europe."
Some are calling for NATO to forge closer relationships with democracies outside the traditional Euro-Atlantic area. Michael Zantovsky, the current Czech ambassador to Israel and key player in his country's accession to NATO a decade ago, called for the alliance to broaden its horizons in a recent speech in Prague.
"Because of the dispersed nature of current security risks and threats, [NATO's] response needs to be dispersed as well, and involve other countries as partners, allies, or would-be members," Zantovsky said, adding that NATO needed to reach out not just to aspiring members like Georgia and Ukraine, but also "countries outside the Atlantic area, such as Japan, Australia, India, some Latin American countries, and, yes, Israel."
RFE/RL correspondent Ron Synovitz contributed to this report
60 Years In Eight Minutes
In Washington in 1949, the North Atlantic Treaty Organization was born. RFE/RL looks at the dramatic and difficult moments in NATO history with rarely seen archive films and exclusive interviews. Play
NATO At 60 series:
Rolling With The Changes
End Of Expansion?
The Article Of Faith
Getting The Balance Right