Pirmieji Lietuvos ir NATO ryšiai užsimezgė dar 1991 metų gruodį, kai Lietuva kartu su kitomis Vidurio Europos valstybėmis buvo pakviesta įkurti Šiaurės Atlanto Bendradarbiavimo Tarybą (NACC), kurios tikslas - Rytų ir Vakarų blokų pasitikėjimo bei bendradarbiavimo stiprinimas.
Iki 1994 metų Lietuva nebuvo oficialiai paskelbusi savo noro įstoti į NATO ir svarstė įvairias saugumo užtikrinimo alternatyvas, tarp jų neutralumo politiką, jungimąsi į kelių mažų valstybių aljansą, dvišalį aljansą su viena iš didžiųjų valstybių ir narystę daugiašaliame kolektyviniame aljanse. Tačiau daugiausia privalumų žadėjo narystė NATO.
Ėmus laikytis nuoseklios integracijos į NATO politikos, 1994 metų sausio 4 dieną Lietuvos prezidentas Algirdas Brazauskas išsiuntė laišką į NATO su oficialiu prašymu priimti Lietuvą į Aljansą.
Tą patį mėnesį Lietuva prisijungė prie Partnerystės taikos labui (PTL) iniciatyvos, lapkritį buvo pasirašyta pirmoji Lietuvos ir NATO Individualios partnerystės programa. PTL programa Lietuvai suteikė galimybę dalyvauti tarptautiniuose mokymuose ir pratybose, plėsti ryšius su Aljansu ir į jį įeinančiomis valstybėmis.
1994 metų birželio 10 dieną Lietuva įteikė NATO pristatomąjį dokumentą, kuriame pateikė integracijos į Aljansą strategiją.
1994 metais buvo įsteigtas Baltijos batalionas (BALTBAT) kartu su Danijos, Švedijos, Norvegijos ir kitų šalių pagalba.
1995 metų sausio 31 dieną Lietuva prisijungė prie PTL programos Gynybos planavimo ir peržiūros proceso. Tai reglamentavo informacijos teikimą Aljansui apie Lietuvos karines pajėgas, mokymo centrus, pastangas siekiant suderinamumo su NATO pajėgomis.
1996 metų pradžioje Lietuva pradėjo dalyvauti NATO vadovaujamoje IFOR ("Taikos įtvirtinimo pajėgų") operacijoje Bosnijoje.
Nuo 1997 metų Lietuva pradėjo aktyviai dalyvauti NATO ir šalių partnerių Euro-Atlanto Partnerystės taryboje, kurioje daug dėmesio skirta PTL programos įgyvendinimui.
Nuo 1997 metų Lietuva, kuri buvo laikoma pasiruošimo stojimui į NATO lydere tarp Baltijos šalių, ėmė propaguoti bent vienos Baltijos šalies priėmimo į NATO idėją.
1997 metų liepą Madride NATO šalių narių vadovų susitikime pažymėta, kad Baltijos valstybės padarė pažangą siekiant saugumo ir stabilumo užtikrinimo Baltijos regione.
1997 rugpjūtį Lietuvos Vyriausybės nutarimu įsteigta šalies misija prie NATO.
1999 metų balandį Vašingtone vykusiame NATO šalių narių vadovų susitikime patvirtinta tolesnė Aljanso atvirų durų politika ir pasveikintos Lietuvos pastangos siekiant narystės organizacijoje.
Susitikime taip pat priimtas Narystės veiksmų planas, kuriame rekomenduojamos pasirengimo narystei Aljanse priemonės politinėje, ekonominėje, gynybos, išteklių, saugumo ir teisinėje srityse. Rugsėjį Aljansui pristatytas Lietuvos pasirengimo narystei planas.
Tais pačiais metais Seime buvo priimtas Krašto apsaugos sistemos strategijos įstatymas, pagal kurį Lietuvos krašto apsaugos sistemos biudžetas iki 2001 metų palaipsniui pasieks NATO šalių narių gynybos biudžetų santykinį vidurkį - 1,95-2 proc. BVP.
2000 metų gegužės 19 dieną Vilniuje devynių NATO valstybių kandidačių Albanijos, Bulgarijos, Estijos, Latvijos, Lietuvos, Makedonijos, Slovėnijos, Slovakijos ir Rumunijos užsienio reikalų ministrai pasirašė "Vilniaus pareiškimą", kuriuo prasidėjo politinis ir praktinis bendradarbiavimas tarp narystės Aljanse siekiančių valstybių. Pareiškimą pasirašiusios valstybės pradėtos vadinti V-9 grupe, o jų bendradarbiavimas - "Vilniaus procesu". "Vilniaus proceso" dalyvių susitikimų tikslas - įtakoti NATO narių sprendimą dėl Aljanso plėtros 2002 metais.
2000 lapkritį Lietuvos prezidento Valdo Adamkaus dekretu Lietuvos integracijos į NATO vyriausiuoju koordinatoriumi paskirtas ambasadorius Giedrius Čekuolis. 2001 sausio 31-vasario 2 dienomis Lietuvoje su darbo vizitu lankėsi NATO ekspertų grupė, kuri vertino, kaip Lietuva vykdo pagal šalies pasirengimo narystei NATO programą 2000-2001 metams prisiimtus įsipareigojimus.
Praėjusių metų gegužę vienuolika Lietuvos parlamentinių partijų pasirašė susitarimą dėl Lietuvos gynybos politikos 2001-2004 metais.
2001 metų gegužės 10-12 dienomis Bratislavoje įvykusioje V-9 premjerų konferencijoje prie grupės prisijungė Kroatija, ir "Vilniaus procesas" tapo V-10 grupe.
2001 m. gegužės 27-31 dienomis Vilniuje vyko NATO Parlamentinės Asamblėjos pavasario sesija, kurioje kalbą pasakė organizacijos generalinis sekretorius lordas Robertsonas.
JAV prezidentas George’as Bushas (Džordžas Bušas) kalboje 2001 metų birželį Varšuvos universitete pareiškė, kad laukia istorinių sprendimų 2002 metų Prahos viršūnių susitikime.
Lapkričio 21 dieną Prahoje NATO viršūnių susitikime Lietuva turėtų būti pakviesta į NATO drauge su dar 6 valstybėmis.
Tikimasi, jog Lietuvos stojimo į NATO sutartis bus pasirašyta 2003 metų pavasarį ir šios organizacijos valstybėse narėse prasidės jos ratifikavimo procesas.
Sutarties ratifikavimas šalių narių parlamentuose gali užtrukti maždaug metus, todėl visateise Aljanso nare Lietuva taps 2004 metų pavasarį.