Mihail Gorbacsov, a Szovjetunió Kommunista Pártja Központi Bizottságának főtitkára, a szovjet Legfelsőbb Tanács Elnökségének elnöke 1988. december 7-én jelentette be az ENSZ Közgyűlésében, hogy a Szovjetunió 1991-ig 25 százalékkal csökkenti kelet-európai haderejét. Magyarországot 1989. április 25-én hagyta el az első szovjet alakulat, a kiskunhalasi 13. harckocsi gárdaosztály.
A rendszerváltozás előestéjén már nemcsak az ellenzéki erők követelték a teljes csapatkivonást, hanem a Németh Miklós vezette kormány is ennek elérésén dolgozott. Azzal azonban mindenki tisztában volt, hogy ezt a cél csak a nagyhatalmak megállapodása után valósítható meg. Gorbacsov és George Bush amerikai elnök 1989. december 2-3-i máltai csúcstalálkozóján aztán lényegében véget ért a jaltai világrend, a Szovjetunió "elengedte" a kelet-európai országokat.
A tárgyalások 1990. február 1-jén kezdődtek meg Budapesten, a magyar delegációt Somogyi Ferenc külügyminisztériumi államtitkár, a szovjetet Ivan Aboimov külügyminiszter-helyettes vezette, a feszült légkörben folyó megbeszélések végső szakaszában megfigyelőként részt vett a parlamenti választásokra országos listát állított 12 párt képviseletében Raffay Ernő (MDF), Demszky Gábor (SZDSZ) és Kósa Lajos (Fidesz) is.
A csapatkivonásról szóló kormányközi egyezményt 1990. március 10-én Horn Gyula magyar és Eduard Sevardnadze szovjet külügyminiszter írta alá Moszkvában. Ennek értelmében 1991. június 30-ig kellett kivonni a teljes személyi állományt, beleértve a szovjet állampolgárságú civileket, valamint a fegyverzetet, a harci technikát és az anyagi eszközöket. A pénzügyi kérdések rendezését a felek későbbre hagyták.
Az első szovjet egység, a Hajmáskéren állomásozó szovjet harckocsizó alakulat két nappal később, 1990. március 12-én indult haza. A Magyarországon állomásozó mintegy százezres szovjet haderő 27 ezer harcjárművel és gépjárművel rendelkezett, ebből 860 volt harckocsi, 600 önjáró tüzérlöveg, 1500 gyalogsági páncélozott harcjármű. Az 560 ezer tonna hadianyagból 230 ezer tonna volt lőszer, 100 ezer tonna üzemanyag, mindezek 60 helyőrségben, katonavárosban, hat repülőtéren helyezkedtek el. A kivonási műveletekkel kapcsolatos tennivalók koordinálásával a kormány Annus Antal vezérőrnagyot, a Magyar Honvédség vezérkari főnökének általános helyettesét bízta meg.
A következő 15 hónapban mintegy 35 ezer vasúti kocsi, másfél ezer szerelvény indult a Szovjetunióba. A felszereléseket, harcászati eszközöket, a lebontott laktanyák épületelemeit a mándoki és a tornyospálcai rakodóállomásokon rakták át a keskeny nyomtávú magyar szerelvényekből a széles nyomtávú szovjet vagonokba, a hatalmas volumenű szállítás a MÁV-nak egymilliárd forintnyi árbevételt hozott.
A csapatkivonást elhúzódó vagyonjogi-pénzügyi vita követte, mert az 1957-es kormányközi egyezmény több kérdést nem tisztázott. A hátrahagyott katonai objektumok át-, illetve visszaadása, leromlott állaga, az okozott környezeti károk körül forgó tárgyalások végül "nulla megoldással" értek véget, a felek kölcsönösen lemondtak egymással szembeni követeléseikről. Az egyezséget 1992. november 11-én Budapesten írta alá Antall József miniszterelnök és Borisz Jelcin orosz elnök.
1991. június 19. nevezetes dátum lett a magyar történelemben: az 1944. március 19-i német megszállás óta először nem állomásozott idegen katona magyar földön. Ennek emlékére 2001. május 8-án az Országgyűlés június 19-ét nemzeti emléknappá, június hónap utolsó szombatját pedig a magyar szabadság napjává nyilvánította.
