1957年6月，反对改革的人开始发起攻击，他们要求赫鲁晓夫辞去苏共第一书记职务。但苏共中央委员会支持他，经过几年的激烈斗争后，他在1961年10月的苏共二十二大上对斯大林发起了更猛烈的攻击。老布尔什维克朵拉·拉祖继娜走上讲台发言。由于她自己忍受了多年的压制，她说列宁托梦给她说红场的陵墓里只能有他一个。全场掌声雷动。一个寂静的夜晚，这件事情开始实施，经过防腐液处理的斯大林的尸体被抬出了陵墓，埋在克里姆林宫的墙底下。在他的墓地上只有一根柱子和一座半身像。历史学家开始查找斯大林与列宁经常争吵、举止粗鲁的材料。斯大林格勒重新命名为伏尔加格勒。对列宁的崇拜，也在不断提升着对赫鲁晓夫的崇拜。1959年出版了新的党史教程。那些崇拜斯大林的党员要么保持沉默，要么被开除党职。只有一小撮在国外的共产党员对此持有异议。他们当中最主要的是中国共产党。***在生活上对斯大林不满，但他认为赫鲁晓夫的改革是与斯大林和***的共产主义决裂。这导致双方关系出现裂痕，最后中苏走向分裂。
赫鲁晓夫1964年下台。苏共政治局（主席团重新变成了政治局）推翻了赫鲁晓夫在国内外实施的诸多政策，政治局也掩盖了不同意见的争论。但这是对赫鲁晓夫政策的修正，不是要回到真正的斯大林主义。新的苏共中央总书记勃列日涅夫从没考虑过实施恐怖统治或个人专制。“稳定干部”成了一句口号。但实际上苏共政治局在1969年斯大林生日这一天打算重新评估斯大林的遗产。《真理报》的社论准备了一份赞美词，只是在最后一分钟由于意大利和法国共产党的干预才没能公开发表。（但这也迟了，蒙古共产党已经印发出去了，因为乌兰巴托的时区要早一些。）
但重评斯大林的动机还在。1984年7月，戈尔巴乔夫上台前，政治局考虑过这个问题。年长的政治局成员对斯大林还是有感情的，对赫鲁晓夫很不满。为斯大林恢复名誉的想法不了了之，因为戈尔巴乔夫在1985年担任党的总书记后，他在政治局不再提这件事了。很快斯大林又成为批判的对象。在戈尔巴乔夫的公开性原则下，斯大林滥用权力的许多材料被揭发出来了。斯大林建立的行政命令制备受指责。电影、小说、诗歌以及历史着作都在指责斯大林。戈尔巴乔夫通过知识分子的着书立说让公众明白，全面评估斯大林的遗产对苏联社会的新生是十分重要的。但这一过程有点失控，因为有些批评斯大林的人认为列宁对权力滥用也负有责任。他们将行政命令制的起源追溯到苏联成立的时候。但在公开讨论中，也有人赞扬斯大林，有人还是肯定了斯大林在二十世纪三十年代苏联工业化以及反法西斯战争胜利中作出的贡献。
