A sztálinista politikusok – élükön Sztálin legközelebbi bajtársával, Vjacseszlav Molotovval – egyenesen Hruscsov személyét kezdték támadni. Bár az SZKP vezetésében a válság régóta érlelődött a háttérben, a magyar felkelés hozta azt a felszínre. Ellenfelei elsősorban azzal vádolták Hruscsovot, hogy elhagyta a világszocializmus ideológiai alapjait. Más vádak is felmerültek, s a krízis odáig fajult, hogy az SZKP KB elfogadott egy határozatot Hruscsov leváltásáról. Hruscsov bajtársai a Központi Bizottságban, a KGB-ben és a hadseregben azonban más döntésre bírták a pártvezetőket, olyannyira, hogy az 1957-es pártértekezleten végül a veterán sztálinistákat, Molotovot, Kagankovot és Malenkovot távolították el.
Ezzel Hruscsov megerősítette saját hatalmát, de nem lépett előre a szovjet hétköznapi élet demokratizálásában. A párton belül a sztálinizmus leleplezése érdekében indított kampánya a személyes hatalomért folytatott harc egy formája volt, s közben a saját felelősségét igyekezett kisebbíteni a harmincas és negyvenes évek elnyomó politikájával kapcsolatban. Ugyanakkor a főtitkár a Szovjetunió és a szocialista tábor új irányítási módjait kereste. Sztálin halála után nyilvánvalóvá vált, hogy a kemény diktatúra és a terror a szocializmus építését zsákutcába vezetik.
1956 decemberében Uljanovszkban, Lenin szülőföldjén Alekszandr Lobiscsev történész-filozófus A magyar tragédia értelme és jelentése címmel írt cikket – amely csak 1991-ben láthatott napvilágot. Lobiscsev szerint „a magyar felkelés nem ellenforradalom, hanem valódi népi, sőt progresszív forradalom volt, függetlenül attól, hogy jelentős ellenforradalmi erők vagy akár egyszerű bűnözők csapódtak hozzá. Az intervenció, a magyar munkások és földművesek elnyomása – ez maga az ellenforradalmi tett.” Véleménye szerint „a sztálinizmusra mért első megrendítő ütés éppen azért olyan fontos, mert azt nem a kapitalisták vitték véghez, hanem a munkások és a haladó szellemű ifjúság. A sztálinizmus napjai meg vannak számlálva”.
A Szovjetunióban a sztálinizmus elleni harc burkoltan folyt ugyan, a hatalom számára azonban életveszélyes volt, ezért nem válogattak az eszközökben. Az önálló kül- és belpolitikai nézetekért továbbra is bebörtönözték az embereket, miközben Hruscsov büszkén hirdette, hogy a Szovjetunióban nincsenek politikai foglyok. Fedor Burlackij híres szovjet író elmondása szerint a magyarországi események után először a „kromalnyikokat” kezdték letartóztatni, vagyis azokat, akik nem tudtak megmaradni a kritika nekik megszabott határain belül. Már akkor divatba jött a nemkívánatos egyedek elmegyógyintézetbe, úgynevezett „pszichóba” küldése. Hruscsov, a sztálinizmus nagy leleplezője nem mondott le annak módszereiről, hanem modernizálta azokat. Nem csupán nem számolta fel teljesen a lágereket, de a hiányzó kapacitást a kórházak pszichiátriai osztályaival pótolta, ahol előszeretettel várták a sztálinista vezetés ellenzőit és a magyarországi forradalom támogatóit.
Erik Judin, az egyik szibériai egyetem filozófiatanára sem értett egyet a szovjet hadsereg budapesti bevetésével. Úgy vélte, a szocialista országoknak jogukban áll a fejlődés útját megválasztani, és erről írt is nővérének. Az elfogott levél alapján Judint szovjetellenes propagandával vádolták meg, és hat év munkatáborra ítélték.
A KGB jelentései beszámoltak arról, hogy a társadalom minden rétegében tapasztalható a magyarországi felkelés támogatása. A nyílt tüntetésekig akkor nem jutott el az elégedetlenség. A lakosság nagyobbik része elhitte a hivatalos propagandát, miszerint a magyarországi felkelés „ellenforradalom”, a magyarok „fasiszta mételytől részegedtek meg”.
A magyarországi felkelés azonban ráijesztett a szovjet vezetésre. Emlékirataiban Nyikita Hruscsov fia, Szergej arról ír, hogy egészen apja 1964-es leváltásáig az SZKP KB-tagok fejében a lövegek budapesti sortüzei visszhangzottak. (A Magyarország lerohanására indított Forgószél hadműveletben a korabeli adatok szerint mintegy hatszáz szovjet katona esett áldozatul, és több ezren megsebesültek – a szerk.) 1956 után Hruscsov gyanakvással reagált minden, a szovjet értelmiség részéről érkező szabadság-igényre. „Itt ti nem hoztok létre semmiféle Petőfi-klubot” – mondogatta, amikor a szovjet kultúra képviselői megpróbálták átlépni a „szocialista realizmus” SZKP által megszabott határait.
A szovjet értelmiség próbálkozásai, hogy nagyobb alkotói szabadságot nyerjenek, gyakran a magyarországi eseményeket választották mottóul. Már 1956 telén egy Budapest című vers keringett a moszkvai és leningrádi művész-értelmiségi körökben, amely üdvözölte a forradalmat, és mélyen elítélte a szovjet beavatkozást. Amint az egyik sor mondja: „Milyen jó, hogy ég ez a mi tankunk.” Elítélte a beavatkozást, és támogatásáról biztosította a despotizmus ellen felkelt magyarokat a később Nobel-díjjal elismert híres fizikus, Lev Landau is.
A szovjet hatalom félelme a magyarországi események megismétlődésétől és egyben visszatérése a sztálini gyakorlathoz 1962-ben érte el csúcspontját. Miután a Minisztertanács harminc százalékkal megemelte a fogyasztási cikkek árát, több városban szovjetellenes röplapok jelentek meg, és forrongás kezdődött. A doni kozákok egykori fővárosában, Novocserkaszkban az áremelés egybeesett egy villanymozdonyokat gyártó óriásvállalat munkabércsökkentésével. A munkások válaszul elüldözték a vezérigazgatót és a helyszínre érkező megyei párttitkárt. A felkelés estéjén budapesti mintára megérkeztek a tankok. Másnap, amikor már több gyár dolgozói virágokkal és Lenin-portrékkal indultak tüntetni, a Moszkvából Novocserkaszkba érkezett hattagú SZKP KB-bizottság a tömegbe lövetett. Hivatalosan húsz halottja volt a felkelésnek, és további hét főt ítéltek halálra. Nem hivatalos adatok szerint azonban egy nagyságrenddel többen vesztették életüket.
1967-ben, három évvel Hruscsov leváltása után a szovjet KGB elnökévé Jurij Andropovot nevezték ki, aki 56-ban a Szovjetunió budapesti nagyköveteként tartotta fenn az összeköttetést a magyar kommunista vezetés és a Kreml között. A hithű sztálinista irányítása alatt a KGB átalakult a párt büntetőosztagává. Andropov – részben a Magyaroszágon tapasztaltak hatására – idegesen reagált minden próbálkozásra, amivel a szovjet lakosság demokratikus szabadságjogokat akart kivívni. A másként gondolkodók elnyomása, a disszidensek ellehetetlenítése, letartóztatások, száműzések, a szovjet állampolgárság megvonása, egészséges emberek pszichiátriai kezeltetése az SZKP bírálata miatt – mindez mindennapos gyakorlat maradt még a Szovjetunió fennállásának legutolsó éveiben is.