改革者面临一种困境：如果他们宣布放弃斯大林的遗产，那他们统治的合法性将会大打折扣，但如果他们不马上实施改革，社会的不满会积聚，他们也会有麻烦。还有更大的困难。有些人崇拜斯大林，但也有几百万人痛恨斯大林的镇压。斯大林死后还阴魂不散。改革者必须意志坚定，措施得力。慌乱必定会扰乱整个苏联的秩序。主席团的大多数成员认为，在不特意批评斯大林的条件下实施改革。[5]在苏共中央委员会的会议上，他们只是提到晚年斯大林的反复无常。贝利亚因捏造英国情报机构代理人的罪名而被逮捕，贝利亚被逮捕后，苏共中央主席团1953年7月召开了会议。实际上领导层担心贝利亚会掌握最高领导权，也担心他会实施看起来相当激进的改革。他们认为，应该对过去所犯下的罪行和权力滥用负责的是贝利亚，而不是斯大林，1953年12月，贝利亚被处决了。[6]
斯大林的家庭也遭受了重大的变故。他的女儿斯维特兰娜很快就改了自己的姓。学生时代大家都知道她的名字叫斯维特兰娜·斯大琳娜（SvetlanaStalina），斯大林死后，她自己改名叫斯维特兰娜·阿利卢耶娃。[7]由于已经向她父亲的继任者低头，所以她最终幸免于难。瓦西里·斯大林并未做相应的改变，经常沉湎酒色，臭名远扬。斯大林实际上已经和他脱离关系了，他父亲死后，他被调查，并因爱胡闹和滥用公共资金而被捕。他的特权年月结束了。
贝利亚倒台后，苏共掌控了内务部。对于各民族有文化自觉权的限制仍然比较多。马林科夫和赫鲁晓夫继续推动改革，也都在为掌握最高权力而斗争。集体农庄的粮食收购价格上涨了。为提高粮食产量，哈萨克斯坦的荒地得到了开发。苏联与南斯拉夫的关系有了一定的缓和，同美国的紧张关系也有所松动，朝鲜战争也结束了。由于要明确支持苏共主席团的每一项活动，所以在中央委员会上对发言管理就不那么严格了。虽说苏联仍然是一党专政，但总体上说，恐怖气氛淡了。马林科夫和赫鲁晓夫之间的竞争还在继续。贝利亚过去一直担心他激进的改革思想和他个人的鲁莽。马林科夫缺乏自信，赫鲁晓夫因镇压贝利亚而名声大振，他在两年的时间里成了苏联的最高领导人。
在赫鲁晓夫的授意下，一个委员会开始调查斯大林时期大清洗的数据。赫鲁晓夫虽然在寻找对马林科夫不利的材料，但这尚需时日。苏共主席团的几位成员反对实施进一步的改革。为了保证自己能顺利接班，赫鲁晓夫在1956年的苏共二十大上提出了斯大林的问题。有人说破坏苏联秩序是危险的，他反驳说：“如果我们不在中央全会上说真话，我们在将来的某个时候可能不得不说出真话。那时候我们不是在发表演讲，而是在接受人民的调查！”[8]在苏共二十大闭幕时，赫鲁晓夫指责斯大林是一个怪人，他整死了几千人，在政治领导和具体政策上破坏了列宁主义的传统。指控书并没有全面综合地评价斯大林。赫鲁晓夫的报告集中在从1934年基诺夫遇害以来斯大林的活动上。他并不直接批评20世纪20年代后期以来苏联建立起来的基本政治经济结构，他也没提及斯大林在内战和第一个五年计划实行期间实施的恐怖。为了赢得当时党政官员的支持，他必须给人一种这样的印象，你们这些人的前任都是1937—1938年大清洗的受害者。
整个会场都没人提反对意见。赫鲁晓夫达到了他的目的：对于他国内的竞争对手来说，很难指责他领导权的合法性，除非这个人想回到斯大林的大恐怖年代。然而还有一个问题，正是斯大林在东欧建立起了共产主义政权。通过指责斯大林，赫鲁晓夫重新确立了一条沿着列宁主义和十月革命的路线前进的道路。这在东欧国家行不通，因为这些国家是斯大林帮助他们建立了共产党政权。赫鲁晓夫的报告对于东欧来说就是一颗政治炸弹。波兰发生了有组织的罢工抗议活动。1956年10月，匈牙利也发生了动乱。
1957年6月，反对改革的人开始发起攻击，他们要求赫鲁晓夫辞去苏共第一书记职务。但苏共中央委员会支持他，经过几年的激烈斗争后，他在1961年10月的苏共二十二大上对斯大林发起了更猛烈的攻击。老布尔什维克朵拉·拉祖继娜（DoraLazurkina）走上讲台发言。由于她自己忍受了多年的压制，她说列宁托梦给她说红场的陵墓里只能有他一个。全场掌声雷动。一个寂静的夜晚，这件事情开始实施，经过防腐液处理的斯大林的尸体被抬出了陵墓，埋在克里姆林宫的墙底下。在他的墓地上只有一根柱子和一座半身像。历史学家开始查找斯大林与列宁经常争吵、举止粗鲁的材料。斯大林格勒重新命名为伏尔加格勒。对列宁的崇拜，也在不断提升着对赫鲁晓夫的崇拜。1959年出版了新的党史教程。[9]那些崇拜斯大林的党员要么保持沉默，要么被开除党职。只有一小撮在国外的共产党员对此持有异议。他们当中最主要的是中国共产党。毛泽东在生活上对斯大林不满，但他认为赫鲁晓夫的改革是与斯大林和毛泽东的共产主义决裂。这导致双方关系出现裂痕，最后中苏走向分裂。