Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder. (10. okt. 2015)
Straks Stalin døde, ble det gitt amnesti til mange politiske fanger, straffeloven ble håndhevet mildere, og utenlandske krigsfanger ble stort sett repatriert.
I forbindelse med det sovjetiske kommunistpartiets 20. partikongress i 1956 tok førstesekretær Nikita Khrusjtsjov et kraftig oppgjør med stalinismeni en historisk tale: Stalin hadde skaffet seg eneveldig makt og hevet seg over partiet og lovene, fremmet en grotesk persondyrkelse, drevet en terrorkampanje som rammet mange uskyldige gjennom de falske Moskva-prosessene, og drevet kollektiv avstraffelse gjennom å fordrive hele folkeslag gjennom etnisk rensning.
Khrusjtsjov avgrenset seg likevel til en kritikk av personen Stalin, han prøvet ikke å analysere de samfunnsmessige årsakene til stalinismen.
Talen var ikke offentlig, men innholdet ble likevel hurtig kjent, både i Sovjetunionen og i utlandet.
For landene i Øst-Europa førte oppgjøret i Moskva til at mange fikk større håp om frihet, og det brøt ut folkelige oppstander i Polen og Ungarn. I Polen fikk kommunistpartiet PZPR ny ledelse, med den mer moderate Gomułka i spissen. I Ungarn fikk kommunistpartiet også ny leder, men Imre Nagy klarte ikke å kontrollere situasjonen, det ble forlangt slutt på den sovjetiske okkupasjonen og utmeldelse av Warszawapakten, og det endte i harde kamper mellom ungarske patrioter og sovjetiske soldater, og mange mennesker ble drept. Den sovjetinnsatte lederen Janos Kadar viste seg likevel på sikt å være en forholdsvis moderat kommunist, som skapte den avslappede «gulasj-kommunismen».
Uroen i Øst-Europa førte til et forsøk fra mer stalinistiske krefter på å avsette Khrusjtsjov, men lyktes ikke. Avstaliniseringen fortsatte, med flere omfattende amnestier for politiske fanger, reduksjon av de enorme sosiale forskjellene fra Stalin-tiden, sosiale tiltak som bedre pensjoner og mer boligbygging og avskaffelse av de brutale arbeidslivslovene.
På den 22. partikongressen i 1961 kom Khrusjtsjov med en klar fordømmelse av Stalin i en åpen tale. Liket av diktatoren ble fjernet fra mausoleet på Den røde plass, og statuer av ham revet i hele østblokken, mens byer og gater oppkalt etter diktatoren ble omdøpt.
Khrusjtsjov ble nedstemt og måtte gå av som førstesekretær og statsminister i 1964. Men på de vel ti årene siden Stalin døde, hadde meget endret seg. Ikke minst var den frykten som tidligere hadde preget de kommunistiske diktaturene blitt mindre, mens levestandarden hadde økt.
Bare i Folkerepublikken Kina og Albania fortsatte Stalin-dyrkelsen. Sovjetunionens fordømmelse av Stalin førte til et brudd mellom Sovjetunionen og Maos diktatur i Kina. Mao beskyldte russerne for «revisjonisme».