A sztálinizmustól való elfordulás három évvel a diktátor halála után következett be, ebben az új szovjet pártvezérnek, Hruscsovnak döntő szerepe volt.
Az 1956-os évben dőlt le a Sztálin-mítosz, ezzel összefüggésben a magyar forradalom rázta meg a kommunista rendszert, majd a szuezi válság globálissá tette a feszültséget. Világtörténelmi nézőpontból a legnagyobb hatású esemény a Szovjetunió Kommunista Pártjának február 14. és 25. között ülésező XX. kongresszusa, azon belül is az utolsó napon a pártvezető Nyikita Hruscsov zárt ajtók mögött elhangzott, Sztálint nyíltan bíráló és rövid idő után kiszivárgott úgynevezett titkos beszéde volt. A kilencvenes évek óta megjelent orosz történeti feldolgozásokból – ezeket a történész Baráth Magdolna foglalta össze (Múltunk, 2006/2.) – kitűnik, hogy a szovjet pártvezetésben milyen folyamatok vezettek el a sztálini despotizmussal való olyan szakításhoz, amely azért megőrizte a kommunista rendszer kontinuitását.
Az első lépés az elítéltek nagyon óvatos rehabilitációjának megkezdése volt, ennek első kezdeményezője a sztálini terror leghírhedtebb alakja, Lavrentyij Berija, a belügy- és állambiztonsági minisztérium vezetője volt, aki eséllyel pályázott a pártvezetői posztra.
Alig három héttel a diktátor halála után, 1953. március 27-én Berija kiadta minisztériuma amnesztiarendeletét. Egy orosz történész adata szerint a Gulagon még az amnesztiát követően is több mint 1 millió 360 ezer ember maradt, közülük „ellenforradalmi bűncselekményért” 448 ezer töltötte a büntetését, s a bebörtönzöttek majdnem 28 százaléka 25 év alatti fiatal volt. A KGB hivatalos adatai szerint 1930 és 1953 között „ellenforradalmi, államellenes bűnök” vádjával 3 millió 778 ezer 234 személyt ítéltek el, akik közül 786 ezer 98 főt kivégeztek.
Berija a rehabilitálások irányításával akarta erősíteni esélyeit az utódlási harcban, s ellenfelei éppen a törvénytelenségeket használták fel a likvidálására. Malenkov, Kaganovics és Hruscsov összefogtak Berija ellen, 1953. június végén letartóztatták, zárt tárgyaláson elítélték, decemberben kivégezték, majd a vádiratot szétküldték a helyi pártszervezeteknek és a külföldi kommunista pártoknak.
Hruscsov végeredményben ügyesen vitte végbe hatalmi játszmáját: 1953 szeptemberében a párt első titkáraként „arca” lett a sztálinizmus óvatos felszámolásának, és azzal egyidejűleg a törvénytelenségeket felhasználta ellenfelei lejáratására.
Hruscsov számára a lépésről lépesre haladó rehabilitációs folyamatban az ugrás 1955 őszén következett be, amikor az állambiztonsági szervek hozzáláttak az 1937 és 1939 között elítélt párt- és állami funkcionáriusok ügyének felülvizsgálatához, és Rugyenko legfőbb ügyész beszámolója nyomán őelőtte is világossá lett, hogy a nagy pereknek semmiféle jogi alapjuk nem volt, a kivégzettek egytől egyig ártatlanok voltak.
A kongresszus előtti hetekig Hruscsov csak azokról a tömeges megtorlásokról akart szólni, amelyeket az 1940-es évek első feléig a párt- és állami vezetők ellen elkövettek, ám a vizsgálatok során olyan tények és számok kerültek a párt elnöksége elé, amelyek Hruscsov szerint megkerülhetetlenné tették Sztálin politikusi értékelését és felelősségnek kimondását a tömeges megtorló intézkedésekben.
Az elnökség 1956. február 9-én szembesült a repressziót kivizsgáló bizottság jelentésével, és feltehetően akkor döntötték el, hogy zárt ülésen Hruscsov adjon egy beszámolót a személyi kultuszról. Hruscsov február 18-án mutatta meg az elnökségnek a beszéd első változatát, és másnap diktálta le azt a szöveget, amely a beszámoló alapjává vált. A beszédben a személyi kultusz áldozatai közül csak a kommunistákról esett szó, sőt Sztálin külön érdemeként említette az ellenzékkel való harcát, s a trockistákat és buharinistákat továbbra is „a nép ellenségeinek” minősítette. Hruscsov, miután részletesen szólt a hatalommal való visszaélésről és a diktátor gaztetteiről, hangsúlyozta, „Sztálin meg volt győződve, hogy ez elengedhetetlen volt, hogy csak így lehetett megvédeni a dolgozók érdekeit az ellenség összeesküvéseivel szemben és az imperialista tábor részéről fenyegető támadásokkal szemben. (…) Nem mondhatjuk, hogy tettei egy őrült zsarnoknak a tettei voltak.”
Ismerve a sztálinizmus égbekiáltó bűneit, a „titkos beszéd” a mai olvasónak akár siralmasan erőtlennek is tetszhet. A szovjet kommunista párt akkori erőviszonyait tekintve azonban megkerülhetetlen Hruscsov személyes teljesítményének elismerése – ez után is négy hónap kellett ahhoz, hogy a párt nyilvános határozatot hozzon „a személyi kultusznak és következményeinek leküzdéséről”. A sztálinizmussal való szakítás minden bizonnyal nélküle is bekövetkezett volna, de nem akkor és talán nem is vértelenül.