Vain viisi päivää Berliinin muurin kaatumisen jälkeen, 14. marraskuuta 1989, Pohjoismaiden neuvoston presidentti Karin Söder puhui Pohjoismaiden neuvoston ylimääräisessä Maarianhaminan-istunnossa Eurooppa-politiikasta:

"Meidän tänne kokoontuessamme eurooppalaisissa naapurimaissamme vaaditaan yhä äänekkäämmin vapautta ja demokratiaa, joita niissä on ollut tähän saakka varsin niukasti. Näillä huudoilla meiltä parempiosaisilta pohjoisilta demokratioilta pyydetään tukea... Pohjoismaiden neuvosto ei voi jäädä pelkäksi sivustakatsojaksi tässä prosessissa."

Pohjoismaiden neuvosto ei tyytynytkään pelkkään sivustakatsojan rooliin. Jo vuonna 1990 – eli ennen Neuvostoliiton hajoamista ja Baltian maiden uudelleen itsenäistymistä – otettiin yhteyttä Baltian maiden parlamentaarikoihin.

Tanskan entinen pääministeri Anker Jørgensen oli jo syyskuussa 1989 ehdottanut, että Pohjoismaiden neuvoston parlamentaarikoista koottaisiin pieni ryhmä, joka matkustaisi Neuvostoliittoon ja Baltiaan keskustellakseen ympäristökysymyksistä. Lokakuussa 1990 viisi kansanedustajaa kävikin sekä Moskovassa että Baltian pääkaupungeissa.

Moskovan kokouksen jälkeen Tanskan valtuuskunnan sihteeri totesi:

"Konservatiiviset voimat ovat nyt sangen voimakkaita, vaikkei niillä olekaan muuta sisältöä kuin vaatimus vanhassa järjestelmässä pitäytymisestä."

Oli kuitenkin muita voimia, jotka halusivat järjestelmän vaihtuvan.

Helmikuussa 1991 Pohjoismaiden neuvoston Kööpenhaminan-istuntoon osallistui Baltian tasavaltojen edustajia, jotka kuukautta aiemmin olivat todistaneet dramaattisia hetkiä Riiassa ja Vilnassa.

Baltian maiden itsenäistyttyä Pohjoismaiden neuvosto aloitti tiiviin yhteistyön uuden sisarjärjestönsä Baltian parlamentaarisen yleiskokouksen kanssa.

Vähitellen yhteistyö myös Venäjän parlamentaarikkojen kanssa tiivistyi.

Yhteistyössä alkoi uusi vaihe, kun Pohjoismaiden neuvoston sihteeristö siirtyi Tukholmasta Kööpenhaminaan vuonna 1996 samaan osoitteeseen Pohjoismaiden ministerineuvoston sihteeristön kanssa.

Yhteistyö kehittyy edelleen, ja Pohjoismaiden neuvosto on solminut yhteyksiä poliitikkoihin lukuisissa maissa Pohjolan ulkopuolella.

Vuodesta 2007 yhteyksiä on ollut myös Valko-Venäjälle, niin oppositioon kuin hallitukseenkin.