După ce, în anii 1944-1948, Armata Roşie avusese un rol important în ascensiunea comuniştilor spre putere, treptat, prezenţa ei a început să-i incomodeze pe liderii politici români, care doreau să se elibereze de sub tutela sovietică şi să devină conducători reali ai României. În mai 1955, Gheorghi-Dej a iniţiat unele discuţii cu membrii Biroului Comitetului Central al Partidului Muncitoresc Român, vizând retragerea trupelor sovietice din România. Această problemă a fost dezbătută în august 1955 în Biroul Politic, care a stabilit ca Gheorghiu-Dej să ridice problema retragerii trupelor sovietice în faţa lui N. S. Hruşciov, primul-secretar al Comitetului Central al Partidului Comunist al U.R.S.S. şi preşedintele Consiliului de Miniştri din Uniunea Sovietică.
Prudent din fire, Gheorghiu-Dej l-a însărcinat pe Emil Bodnăraş
– membru în Biroul Politic şi ministrul forţelor armate – să discute cu Hruşciov deoarece acesta se bucura, datorită trecutului său, de o deosebită încredere din partea Moscovei. Astfel, problema retragerii trupelor sovietice a fost ridicată cu prilejul vizitei lui Hruşciov în România, în zilele de 21-26 august 1955. Luat prin surprindere, Hruşciov a reacţionat dur. Cu toate acestea, chestiunea retragerii Armatei Roşii din România era pusă şi a devenit obiect de preocupare pentru conducerea sovietică.
Un pas important pe calea construirii unei imagini pozitive a noii conduceri sovietice care îl avea în frunte pe N. S. Hruşciov a fost marcat de condamnarea stalinismului la Congresul al XX-lea al Partidului Comunist din Uniunea Sovietică (februarie 1956).
Relaxarea internaţională în raporturile dintre U.R.S.S. şi statele socialiste a creat popoarelor din aceste ţări iluzia că se puteau desprinde din sfera de dominaţie sovietică. În toamna anului 1956 au avut loc mari mişcări sociale, politice şi naţionale în Polonia şi Ungaria.
În acest context, la 15 aprilie 1957, a fost semnat, la nivelul miniştrilor de externe, Acordul referitor la statutul juridic al trupelor sovietice, staţionate temporar pe teritoriul României, urmat de mai multe convenţii speciale, referitoare la acordarea ajutorului reciproc în problemele urmăririi şi judecării infracţiunilor şi în rezolvarea proceselor civile, ivite în legătură cu staţionarea trupelor sovietice, la modul şi condiţiile de folosire a cazărmilor, clădirilor de serviciu, depozitelor, la efectivele trupelor sovietice şi locurile lorde dislocare ş.a.
Un alt pas pe calea normalizării raporturilor între cele două state s-a realizat prin desfiinţarea sovrom-urilor şi plecarea consilierilor sovietici, începând cu luna februarie 1957.
Considerând că avea şanse de reuşită, Gheorghiu-Dej a avut o discuţie cu Hruşciov, în care a arătat că adversarii Uniunii Sovietice apreciau că regimul socialist din România se menţinea numai datorită tancurilor sovietice; liderul politic român a sugerat că ar fi fost bine să se demonstreze lumii capitaliste că socialismul se baza pe „încrederea poporului”.
Era o ideea la care liderul sovietic s-a dovedit a fi deosebit de sensibil, deoarece Uniunea Sovietică era acuzată că impusese regimuri politice nepopulare în zona Europei Centrale şi de sud-est, care se menţineau numai cu sprijinul Armatei Roşii. Intervenţia militară sovietică din octombrie 1956 în Ungaria era considerată drept cea mai clară dovadă a acestei realităţi. În consecinţă, Hruşciov a ajuns să aprecieze că retragerea trupelor sovietice din România ar putea constitui un excelent mijloc de propagandă pentru guvernul de la Moscova, în sensul că acţiona pentru detensionarea situaţiei internaţionale, oferind un exemplu demn de urmat şi de statele din N.A.T.O. şi în primul rând de S.U.A. Pe de altă parte, U.R.S.S. dispunea de un arsenal militar care putea acţiona de pe teritoriul propriu, fără a mai fi nevoie de prezenţa trupelor sovietice în România. În această perioadă, Hruşciov era prezentat de propaganda oficială sovietică drept un mare „campion al păcii”.
În ziua de 24 mai 1958, Comitetul Politic Consultativ al statelor membre ale Tratatului de la Varşovia, într-o consfătuire desfăşurată la Moscova, a aprobat propunerea guvernului sovietic, pusă de acord cu guvernul de la Bucureşti, cu privire la retragerea de pe teritoriul României a trupelor Armatei Roşii. Pe această bază s-a semnat un Acord între Ministerul Forţelor Armate ale R.P.R. şi Ministerul Apărării al U.R.S.S. referitor la modalităţile retragerii trupelor sovietice din România în U.R.S.S., în perioada 15 iunie – 15 august 1958.
România a fost singura ţară socialistă din care s-au retras trupele sovietice. Din acest moment, România a pornit, ezitant, pe calea afirmării independenţei şi suveranităţii sale, a restabilirii legăturilor ce-i fuseseră interzise după căderea „cortinei de fier”. Ieşirea de sub hegemonia sovietică a necesitat multă abilitate politică, pentru a nu provoca o reacţie dură din partea marelui vecin de la răsărit. Treptat statele occidentale au început să privească cu interes acţiunile României, transmiţându-i semnale încurajatoare, în speranţa că avea să se realizeze o „fisură” în „blocul sovietic”.
Din septembrie 1958, la cererea Comitetului Central al Partidului Muncitoresc Român, conducerea de la Moscova a început să-şi retragă consilierii din România (cu excepţia câtorva specialişti militari), iar autorităţile române au putut acţiona mai relaxat, începând un proces de reconsiderare a politicii interne şi externe.