Nato-Venäjä-neuvosto perustettiin 28.5.2002 presidentti Vladimir Putinin ja Naton jäsenmaiden edustajien allekirjoituksella. Foorumin tarkoituksena oli neuvottelu, yhteistyö, päätöksenteko ja yhteinen toiminta tasavertaisina kumppaneina alueilla, joissa Nato-mailla ja Venäjällä oli yhteistä etua turvallisuusasioissa.
Kansan Uutisissa kerrottiin neuvoston perustamisen jälkeen, että Naton uudet jäsenmaat Puola,Tšekki ja Unkari eivät ole kovin innostuneita asiasta. ”Se, että Venäjä, joka vastusti niiden jäsenyyttä Natossa, on nyt mukana puolustusliiton päätöksenteossa, aiheuttaa luonnollisesti epäilyjä näissä vielä tuoreissa jäsenmaissa.”
Maiden johtajat ilmaisivat kyllä tyytyväisyytensä neuvoston perustamisesta, mutta samalla he pelkäsivät, että niiden ehdotukset Naton kehittämisestä saatetaan torjua Venäjää ärsyttävinä.
Neuvoston perustamiskokouksessa Puolan presidentti Aleksander Kwasniewski vakuutti, että Naton ja Venäjän yhteistyö lisää turvallisuutta ja vähentää Puolan pelkoja Venäjää kohtaan. Hän kuitenkin lisäsi, että Puolalle tärkeää on myös Naton laajeneminen Puolan naapurimaihin ja sen yhteistyö Ukrainan kanssa.
Puola oli ainoa Naton jäsenmaa, joka tuki Ukrainan jäsenyyttä, ja epäili neuvoston perustamisen heikentävän Ukrainan mahdollisuuksia päästä sotilasliiton jäseneksi.
”Puolalaisen tulkinnan mukaan Natossa Ukrainan jäsenyyteen suhtaudutaan vastahakoisesti, koska ei haluta ärsyttää Venäjää, joka ei halua Ukrainaa Natoon.”
”Maan jäsenyys saattaisi vähentää Venäjän vakuutusta puolustusliitossa ja lisätä Ukrainan riippumattomuutta Venäjästä. Halun miellyttää Venäjää uskotaan olevan myös sen viileyden taustalla, jolla Naton pääsihteeri George Robertson suhtautuu Ukrainan jäsenpyrkimyksiin.”
Ukraina haki Naton jäsenyyttä 23.5.2002.
uutiskirje 
