Lupta pentru succesiune la conducerea statului s-a încheiat în 1956 cu triumful lui Nichita Hrusciov.
Hruşciov şi-a început campania de “destalinizare” la Congresul XX al Partidului, în februarie 1956, congres la care au participat peste 1000 de membri de partid. Într-un discurs de patru ore, noul lider sovietic a dezvăluit actele de brutalitate comise de Stalin. Atitudinea critică a lui Hruşciov viza în primul rând sângeroasele epurări din anii ‘30, persecuţia minorităţilor, cum era cazul tătarilor din Crimeea şi greşelile lui Stalin atât de scump plătite în privinţa liniei politice urmate în cele de-al doilea război mondial. Discursul lui Hruşciov şi direcţia politică adoptată de el ulterior indicau faptul că era adeptul versiunii moderate a noii orientări, pe care o lega de lupta împotriva staliniştilor şi a mitului lui Stalin. Până la sfârşitul epocii sovietice, liderii comunişti s-au împărţit în stalinişti dornici să menţină cît mai mult din vechiul sistem şi reformişti care luptau pentru o dictatură mai puţin rigidă. Sub conducerea lui Hruşciov, cei care au avut câştig de cauză au fost reformatorii.
În mai puţin de doi ani de la discursul antistalinist al lui Hruşciov, lagărele din Siberia erau practic pustii. Controlul strict asupra activităţii politice se menţinuse, însă teroarea luase sfârşit.
Lupta pentru eliberare în estul Europei, 1953-1968.
Est-europenii s-au opus dominaţiei sovietice încă de la începutul perioadei de ocupaţie şi până la prăbuşirea sistemului, în 1989. Stalin i-a împiedicat pe principalii lideri politici din aceste ţări să se împotrivească făţiş, dar forţele secrete de opoziţie au devenit şi mai puternice. La trei luni după moartea lui Stalin au izbucnit revolte în Cehoslovacia şi Germania Democrată (iunie 1953). Armata sovietică s-a grăbit să înăbuşe aceste tulburări, dar în Europa de Est erau pe cale să se declanşeze alte două mişcări de protest.
Timp de trei ani după revoltele din Cehoslovacia şi Germania Democrată, nemulţumirile au continuat să crească în rândul artiştilor şi intelectualilor polonezi. Ei respectau principiile marxiste, dar se opuneau variantei de comunism instaurate de guvernul lor. Liderii comunişti polonezi s-au confruntat cu o ameninţare şi mai serioasă atunci când destalinizarea şi condiţiile grele de existenţă au dat naştere unui violent protest muncitoresc. La 28 iunie 1956, muncitorii din Poznan s-au răzvrătit în număr atât de mare, încât guvernul a recurs la armată pentru a înăbuşi revolta. Criza s-a agravat în momentul în care soldaţii au refuzat să tragă în grevişti. Până la urmă un mare număr de trupe de securitate a pus capăt tulburărilor. Evenimentele din Ungaria, din noiembrie 1956, după o lungă perioadă de agitaţie începută în 1953, au fost cele mai grave. Trupele sovietice de intervenţie au trebuit să facă faţă unei adevărate insurecţii. Înăbuşirea ei a făcut 20.000 morţi. După înfrângerea rebelilor, sovieticii l-au instalat în fruntea statului pe Janos Kadar, apoi l-au arestat pe Imre Nagy şi l- au executat în 1958.