Frustrarea legată de inițiativa anti-Stalin a lui Hrușciov poate fi considerată primul pas în derularea ulterioară a disputei româno-sovietice. După momentul ’56 știut, comuniștii români au avut mai multe în comun cu China lui Mao și Albania lui Hoxha decât cu Polonia lui Gomułka. Cu toate acestea, Gheorghiu-Dej și-a folosit abilitățile diplomatice pentru a îmbunătăți relația țării sale cu Iugoslavia, pe ai cărei lideri îi stigmatizase la întâlnirea Cominform din noiembrie 1949 ca „bandă de asasini și spioni”. Bazat pe declarații ulterioare și confesiuni nepremeditate, în special asupra a ceea ce a fost dezvăluit în timpul Plenarei CC din noiembrie–decembrie 1961, membrii delegației române la Congresul XX al PCUS și-au petrecut serile jucând domino, încercând să-și dea seama ce se petrece la vârful partidului sovietic.
Altfel spus, după Congresul XX, liderii comuniști români au fost derutați, confuzi, traumatizați și, în cele din urmă, scandalizați; întreaga lor lume se prăbușea odată cu idolul lor, Stalin, și cu portretizarea lui ca monstru paranoid, criminal și nimeni militar. Oricare vor fi fost sentimentele sale față de Hrușciov înainte de februarie 1956, este evident că, din acel moment încolo, Gheorghiu-Dej l-a suspectat profund pe Primul Secretar sovietic. Pentru el, la fel ca pentru Thorez, Novotný sau Ulbricht, distrugerea mitului lui Stalin a fost o eroare strategică și ideologică majoră, un cadou nemeritat pentru propaganda imperialistă și o concesie făcută „coruptului revizionism” titoist.
După ce au citit textul complet al Raportului Secret al lui Nikita Hrușciov, participanții români la Congresul XX au trebuit să determine cum anume vor discuta aceste documente cu restul conducerii PMR. Și de vreme ce noua linie adoptată la Kremlin îl primejduia personal, Gheorghiu-Dej a trebuit să tergiverseze dezbaterile care amenințau să apară la nivelul conducerii partidului său. Ca atare, el a invocat criza din Partidul Comunist Grec și implicarea lui de o lună în acea luptă de partid. În fapt, el câștiga timp amăgind diferiți membri ai Politburo-ului, evaluându-le atitudinile și calculând strategia optimă pentru iminentele discuții. În acest efort, Dej conta în special pe sprijinul lui Gheorghe Apostol, Chivu Stoica, Alexandru Moghioroș, Petre Borilă, Emil Bodnăraș, Alexandru Drăghici și, avea motive să spere, Nicolae Ceaușescu. Cât despre camuflajul ideologic al efortului de a preîntâmpina destalinizarea, Gheorghiu-Dej era sigur că se poate baza pe sofismele dialectice ale lui Leonte Răutu.
În cele din urmă, în perioada martie-aprilie 1956, au fost convocate mai multe întâlniri ale Comitetului Central pentru a informa conducerea de partid cu privire la Congresul XX al PCUS. Aceste sesiuni atent orchestrate se doreau a fi un fel de ritual de purificare în care fiecare membru al eșalonului suprem comunist era pus să se angajeze în practica leninistă notorie a criticii și autocriticii. La Plenara din 23–25 martie, Gheorghiu-Dej a prezentat un Raport al Biroului Politic (Dare de seamă) în care îl critica pe Stalin și în special practica cultului personalității. Chiar și așa, Raportul Secret n-a fost explicit menționat. Cât privește manifestările staliniste din cadrul propriului său partid, Gheorghiu-Dej a vorbit despre staliniștii români fără a da nume, sugerând că singurii staliniști din România fuseseră denigrații Pauker, Luca și Georgescu și că el, Gheorghiu-Dej, merita felicitat pentru a fi început destalinizarea avant la lettre, cu mult înainte de Congresul al XX-lea. De asemenea, el a subliniat că al Doilea Congres al PMR (decembrie 1955) a marcat o nouă fază a conducerii colective și că centralismul democratic guverna într-adevăr viața internă din partid. Mai simplu spus, jocul lui Gheorghiu-Dej era acela de a invoca lupta împotriva epuratei facțiuni moscovite ca argument în favoarea comportamentului politic, pasămite „vizionar corect”, al grupului său.