Sotilasliiton laajennuskysymys ja kumppanuudet
Laajentuminen käynnistyi
Naton kylmän sodan jälkeinen laajeneminen käynnistyi pitkän empimisen jälkeen 1990-luvun lopulla, kun jäseniksi hyväksyttiin entisistä Varsovan liiton maista Puola, Unkari ja Tshekin tasavalta. Seuraava laajenemiskierros oli vuonna 2004, jolloin Varsovan liiton maista Natoon liittyivät Slovakia, Bulgaria ja Romania sekä aikoinaan Neuvostoliittoon kuuluneet Baltian maat Viro, Latvia ja Liettua. Entisestä Jugoslaviasta Naton jäseneksi otettiin tässä vaiheessa Slovenia.
Varsovan liitosta länteen
Sotilasliiton laajentuminen itäiseen Eurooppaan aiheutui monista syistä. Neuvostoliiton vaikutuspiirissä eläneiden maiden kansalaiset halusivat mahdollisimman nopeasti mukaan läntisiin liittoihin, jolloin liittyminen Natoon oli teknisesti huomattavasti helpompaa kuin Euroopan unionin jäsenyyden saaminen. Jäsenyyttä hakeneissa maissa Natoa pidettiin sekä suojan antajana Venäjää vastaan että ensiaskeleena kohti EU-jäsenyyttä. Naton jäsenyys oli nopeammin saavutettavissa kuin Euroopan unionin, jonka kanssa neuvottelut kestivät selvästi kauemmin, ja sinä aikana vaadittiin myös laajoja lainsäädännön uudistuksia.
Vaatimuksia uusille jäsenmaille
Yhdysvallat oli vielä 1990-luvun alussa vastustanut Naton laajentamista, mutta vuosikymmenen puolivälissä kanta kuitenkin muuttui. Sekä Natossa että Euroopan unionissa alettiin laajentumista itään perustella tarpeella vakauttaa Itä-Euroopan tilannetta tarjoamalla jäsenyyttä lännen liitoissa. Näin houkuteltiin kandidaattimaita tekemään yhteiskunnallisia ja asevoimia koskevia muutoksia, joihin sisältyi erityisesti vaatimus demokratian ja oikeusvaltioperiaatteen vakiinnuttamisesta.
Asevoimien demokraattisen kontrollin lisäksi uusilta jäseniltä vaadittiin kykyä osallistua Naton toimintaan kriisinhallintatehtävissä. Lisäksi oli määrä nostaa puolustusmenot kahteen prosenttiin BKT:sta. Käytännössä näistä vaatimuksista jouduttiin joustamaan, joten uusien jäsenmaiden tarjoama apu tai voimanlisä Natolle jäi vähäiseksi.
Rauhankumppanuusohjelmaa (PfP) jatkettiin
Rauhankumppanuusohjelmaa (PfP) edelleen jatkettiin, vaikka sen merkitys entisten Varsovan liiton maiden sopeuttajana Nato-jäsenyyteen jäi taka-alalle. Euroopan puolueettomat maat osallistuivat kumppanuusohjelmiin samoin kuin Jugoslaviaan ja Neuvostoliittoon kuuluneet maat, joskin niiden kiinnostus vaihteli suuresti.
Venäjä vastusti Naton laajenemista
Venäjä vastusti Naton laajennusta rajoilleen, mikä vaikutti kiristävästi sen suhteisiin länteen. Yhdysvalloissa ja sen liittolaismaissa pyrittiin yhä välttämään Naton laajennuksesta Venäjän-suhteisiin seuraavia vaikeuksia vakuuttamalla, että laajennus ei ollut suunnattu ketään vastaan ja pidättymällä toistaiseksi ulottamasta sotilasliiton toimintoja kovin näyttävästi uusiin jäsenmaihin. Naton ja Venäjän välinen neuvosto pyrki ratkomaan syntyneitä ongelmia ja kehittämään kumppanuutta, mutta sen toimintakyky oli alttiina poliittisten suhdanteiden vaihtelulle.
Yhdysvallat vaati laajennuksen jatkamista
Yhdysvalloissa nähtiin Irakin sodan alkuvaiheen erimielisyyksien jälkeen hyödylliseksi laajentaa Natoa Romaniaan ja Bulgariaan, koska niiden alueelta voitiin toimia Lähi-idän suunnalle. Näiden maiden jäsenyys toteutui jo vuonna 2004. Yhdysvallat painosti liittolaisiaan hyväksymään myös Ukrainan ja Georgian jäsenkandidaattien listalle, mutta erityisesti Saksassa ja Ranskassa tätä vastustettiin.
Vuonna 2007 liittolaiset kuitenkin taipuivat antamaan lupauksen Ukrainan ja Georgian jäsenyydestä, joskaan mitään aikamäärää ei asetettu. Elokuussa 2008 Georgiassa käydyn sodan johdosta maan jäsenyyshanke lykkääntyi kauaksi eteen päin. Runsaan vuoden kuluttua myös Ukrainan Nato-jäsenyyden hakemus jäädytettiin hallituksenvaihdoksen jälkeen. Ukrainassa kansalaisten enemmistö on
vastustanut liittymistä Natoon.
Laajennus Balkanille
Laajennus Balkanille koettiin huomattavastihelpommaksi, joten Albania ja Kroatia hyväksyttiin Naton jäseniksi keväällä 2009. Seuraavana vuonna Natossa keskityttiin ensi sijassa Afganistanin sodan käymiseen ja Venäjä-suhteiden hoitoon, joten laajennuskysymys jätettiin taka-alalle. Siihen vaikuttivat myös koetut takaiskut Georgian ja Ukrainan jäsenyyskysymyksessä ja liiton jäsenmaiden kansalaisten haluttomuus ottaa uusia vastuita idässä. Monien mielestä Nato oli saavuttanut Itä-Euroopassa jo luontaiset rajansa, joten niiden yli meneminen ja riskien kasvattaminen Venäjän-suhteissa ei houkutellut.