“秘密报告”的公开出版也许会更进一步促进与斯大林主义历史的决裂。不过，彻底管制也许可能会防止随后不久产生的动荡。赫鲁晓夫想进一步公开，而其他人则意见相左，于是他们双方进行了妥协，选择采取中间路线。但赫鲁晓夫仍觉得心有不甘。“他是在斯大林主义的浪潮中爬上权力巅峰的，”他的女儿拉达说：“他的英雄主义在于他能依靠自己的力量实现超越。但是在很多事情上，他还是认为斯大林是正确的，因为他觉得自己就像斯大林。”阿历克赛·阿朱别依说，在“秘密报告”公布后不久，“赫鲁晓夫就已经觉出这次出击力量太过强大了。他暂时仍继续谴责斯大林的暴行，披露新的事实，以佐证他在报告里所说的血腥恐怖，但他越来越控制自己批判性评论的范围，以避免社会出现两种极端势力。……”
“现在那些被捕入狱的人将要回来了，”诗人安娜·阿赫玛托娃（Anna Akhmatova）1956年3月说：“两个俄国人就要见面了，一个是送别的，一个是被送到劳改营里的。”在无数宣读和讨论“秘密报告”的会议上，对斯大林的批判渐渐超出了赫鲁晓夫的限定范围。反斯大林主义者直指赫鲁晓夫尽力避开的痛点：为什么用了这么长时间才说出斯大林的罪行？难道现任主席团成员里就没有帮凶？赫鲁晓夫本人表现如何？他为什么长时间保持沉默，而只在斯大林去世后才大肆攻击？为什么赫鲁晓夫没有对斯大林的非共产党人受害者表示同情和悲痛？苏联制度本身是否就是个错误？
在一些会议上就一些直到20世纪80年代末才重新公开讨论的问题通过了或试图通过决议：人民需要真正的权利与自由，需要进行多党选举以保证这些权利。莫斯科大学的党委书记试图驱逐挤进来听赫鲁晓夫报告的非党人士，结果使会议乱成了一团糟。在科学院的热敏技术实验室里，大家对一位年轻同事的讲话报以热烈的掌声，他说：“我们的权力掌握在一帮无赖恶棍手里。我们的党充满了奴隶精神。”当会议主持者想打断他们的讨论时，差不多有一半的与会者对党纪大加嘲讽，并投票表决要继续讨论。不知是没有接到赫鲁晓夫的口谕，还是接到了但没放在心上，高加索地区的苏维埃社会主义共和国卡巴尔德自治区的地方官员竟敢向党员积极分子通报1937年底该地区被逮捕和被处决的人数，向他们描述了用于严刑逼供的各种残酷手段，并说出了那些应该为此负责的人。在西伯利亚，一位年轻的共青团干部向学生们大声宣读赫鲁晓夫的报告，但当他读完后却不知道应该说些什么，于是他向当地党组织负责宣传工作的领导求援，这位领导也不知道说什么才好，只好让学生们去找他们的物理教师。
4月，克格勃报告说斯大林的画像与半身像已经被推倒或是被涂抹。在一次会议上，共产党员曾试图宣布斯大林是“人民的敌人”。还有一次会议的与会者要求将斯大林的遗体从列宁-斯大林陵墓里移走。但维护斯大林的人数更加众多，一位年轻的共青团官员米哈伊尔·戈尔巴乔夫在俄罗斯南部斯塔夫罗波尔附近的一个农村地区向大家作关于第二十届党代会的报告时就发现了这一情况。当他所在的党组书记提醒他“人们不理解，他们不会接受”时，戈尔巴乔夫推测他指的是共产党员，而不是普通的公民。但是为期两周的每天会议使他转变了观念。年轻一些、受过良好教育的人，特别是那些曾经是斯大林的受害者或是对斯大林的暴行有所了解的人，好像对赫鲁晓夫的“秘密报告”持赞同立场。有一部分人“拒绝相信……或是反对对他的评价”，还有一部分人则是不停地追问：“这是为什么？为什么要把个人的污点暴露在光天化日之下？”最具讽刺性的反应来自一些普通的群众，他们对斯大林感恩戴德，因为斯大林“惩罚了”（其实是清洗）压迫他们的党和警察机构的官员。“他们给我们带来的只是泪水。”戈尔巴乔夫的听众们说。戈尔巴乔夫回忆说：“这就发生在经历过30年代可怕磨难与血腥暴行的地区。”[16]
斯大林的出生地格鲁吉亚比其他任何地方经受的血腥都要多，但奇怪的是，其他任何地方都没有格鲁吉亚那样对斯大林表现出如此的忠诚。在纪念斯大林逝世三周年之际，格鲁吉亚人在第比利斯和其他几座城市的大街上举行集会。刚开始时对斯大林的和平悼念后来演变成了反对赫鲁晓夫“秘密报告”的四天游行示威。有超过六万人手捧鲜花来到第比利斯的斯大林纪念碑前，同时有数以百计的人高举斯大林的画像乘坐卡车在市里游行，并征用了公共汽车、有轨电车和无轨电车。“伟大的斯大林万岁！”“打倒赫鲁晓夫！”“莫洛托夫担任总理！”“莫洛托夫领导苏联共产党！”一些示威者甚至要求格鲁吉亚从苏联分离出去。当他们游行到广播电台时，部队和坦克开了过来。单单在两次冲突中（其中一次发生在斯大林纪念碑前）就有15人被打死，54人受伤，有5人随后死亡。最后至少有20名示威者被打死，60人受伤，被捕入狱的人更多。谢尔盖·赫鲁晓夫记得，当冲突刚刚开始时，他父亲料想年轻的示威者“刚开始会大闹一场，然后会平静下来”。但最后“我们还是进行了很严厉的干预”，赫鲁晓夫告诉南斯拉夫大使米库诺维奇说。“有一小部分人”被打死或打伤，他说，其他人表示了忏悔，答应会收敛自己的言行。从现在开始，赫鲁晓夫补充说：“我们不会没有防范了。”
主席团对热敏技术实验室喧闹的党组会议所作出的反应是向全国的共产党员下发了一份决议。决议谴责了“这种充满敌意的感情爆发”，解散了实验室党小组，开除了党小组所有的成员，“只有那些确实能坚持党的总路线的人”才能被重新吸收入党。[17]《真理报》不指名地严厉批评了那些因为“诽谤捏造”、“反党言论”和“非党声明”而犯有过错的共产党员，并要求结束“这种过度的自由化倾向”，防止出现“反党诽谤言论”。4月7日，这份党报又刊登了中国媒体上的一篇社论，这篇社论呼吁共产党员要学习并珍视斯大林著作及其“历史遗产”。赫鲁晓夫的退让于6月30日达到了顶点，那天中央委员会通过的决议实际上否定了他的“秘密报告”，他的那些斯大林主义同事其实对他所炮制的“秘密报告”感到幸灾乐祸。这份决议以干巴巴、似乎客观的语气谴责了斯大林所犯的“严重错误”，但反对任何“从苏联社会制度的本质中寻找这种个人崇拜原因”的努力，并高度赞扬了“具有列宁主义核心的领导人在斯大林去世后不久就确立了坚持与个人崇拜作斗争的路线”。[18]
但所有这些文件都没有中止由于斯大林而遭到迫害的普通受害者的平反昭雪工作。事实上，这一步伐还加快了，在党代会前，落实平反政策的大约为7000人，党代会后已经达到几十万了。在差不多近百个苏联最高苏维埃调查组的帮助下，释放犯人的工作在继续，这些调查组前往劳改营“审查对那些被指控犯有政治罪行的人的判决根据”。[19]但是当涉及一些著名的受害人时，赫鲁晓夫退缩了。1955年任命的一个对图哈契夫斯基元帅和其他一些将军被清洗进行重新审查的调查组在结束他们的工作后，于1957年1月宣布了为他们平反的决定。但是另一个由莫洛托夫担任主席，卡冈诺维奇、伏罗希洛夫以及其他一些人为成员的委员会负责对季诺维耶夫、加米涅夫、布哈林以及其他人的案件进行重新调查，这个委员会在争论了七个月后拿出了一份报告认为，重新审理这些案件“没有依据”，因为这些被告人“领导了一场反对苏联社会主义建设的反苏斗争”。[20]1957年7月，在反对赫鲁晓夫的政变图谋失败后，他承诺重新审理这些案件，但他后来再也没有提起过此事，因为他对曾经对清洗政策表示赞同的外国共产党领导人不相信，他本人以前也曾相信这一政策的正确性。
赫鲁晓夫想让这种去斯大林主义化继续进行下去，尽管是以更加谨慎的步伐。但是当莫洛托夫坚持6月30日的中央委员会声明时，他也只好接受。两个月前，南斯拉夫特使米库诺维奇在“五一节”的午餐聚会上对苏联领导人之间的紧张关系已经有所了解。在观看了从列宁-斯大林纪念碑出发的游行队伍后，苏联领导人和外国客人被安排参加一个盛大的宴会。作为东道主，赫鲁晓夫在宴会上临时准备了12-15句祝酒词。然后他开始对斯大林进行严厉的谴责，其间还不时地征求莫洛托夫和伏罗希洛夫的意见。他表面上维护他的同事（莫洛托夫是个诚实的共产党员，伏罗希洛夫肯定不是斯大林所说的英国代理人），但实际上却是将他们两人与已故的独裁者联系在了一起。在布尔加宁敦促他只谈斯大林的问题后，赫鲁晓夫对他发表“秘密报告”的理由进行了解释——根据米库诺维奇的说法，因为“他［赫鲁晓夫］已经不再年轻了，随时都可能撒手人寰”，因为“在他离开这个世界前，所有人都会对他的所作所为以及行为方式作出评价”。
被赫鲁晓夫表现出来的明显感情所感动，大使们报以热烈的掌声，这使得他的同事们的反应更加引人注目了。只有布尔加宁和米高扬好像表示赞同，莫洛托夫、马林科夫和卡冈诺维奇“自始至终表现得很消极”。米库诺维奇对莫洛托夫的表现尤其感到奇怪，他们两人的座位紧挨着：“在我看来，赫鲁晓夫好像时不时触及了他的痛处。”很显然，主席团成员们“简直不能再互相忍受了”。莫洛托夫和马林科夫几乎不能再忍受“赫鲁晓夫发挥主人和东道主作用时的那种意味和志得意满了”。[21]
6月，赫鲁晓夫对他的批评者发起了反攻。6月1日，南斯拉夫总统铁托对苏联进行为期23天的访问。就在这一天，莫洛托夫被迫退出了他自1939年以来一直主持的外交部（除了在斯大林的最后岁月里有四年的间断外），赫鲁晓夫的门徒谢皮洛夫接任了外交部长。七天后，卡冈诺维奇从国家薪金委员会主席的位置上退了下来。虽然两人还继续留在主席团里，但他们的解职表明赫鲁晓夫已经经受住了这场风暴的考验。他与铁托的交谈看起来就是一种胜利的表示，两位领导人即兴去高尔基大街进行访问（结果他们两人的口袋里一个铜板也没有）。在欢乐的宴会上，苏联领导人，包括莫洛托夫在内，都轮流谴责斯大林对待南斯拉夫的方式。赫鲁晓夫亲自陪同铁托去了斯大林格勒和黑海。不过，南斯拉夫人实际上拒绝了赫鲁晓夫让他们与莫斯科走得更近的压力。在铁托离开莫斯科的五天后，波兰城市波兹南的工人发起了一场大罢工，要求“面包与自由”，波兰政府出动了数千人的部队和安全部队，在打死了至少53人、打伤数百人后，罢工才得以平息。五个月后，匈牙利爆发了更为激烈的骚乱。
东欧骚乱更深层次的根源与波兰和匈牙利对俄罗斯统治的长期不满有关，特别是第二次世界大战后他们被迫推行斯大林主义。在这两个国家里，共产党都不是通过真正的自由选举上台的。由波勒斯洛·贝鲁特（Boleslaw Bierut）领导的波兰共产党领导层并没有完全将斯大林主义推向极致，包括农业的强制集体化，并拒绝从肉体上消灭被清洗的共产党领导人瓦拉迪斯洛·哥穆尔卡（Wladyslaw Gomulka）。匈牙利的马蒂亚斯·拉科什却极力仿效斯大林，对被废黜的斯大林主义领导人拉兹洛·拉吉克（Laszlo Rajk）进行了公开审判与处决。
斯大林去世后，苏联坚持通过改革削弱波兰与匈牙利政权。华沙领导层的团结一致使其有时间进行自我调整，以适应新的时代。莫斯科允许拉科什继续执政，但坚持他必须接受具有改革思想的伊马雷·纳吉（Imre Nagy）担任总理。拉科什阴谋推翻纳吉，最终利用马林科夫下台的机会于1955年成功地将纳吉赶下了台。与马林科夫一样，纳吉被指控的罪名是“右翼分离主义”，被解除了政府首脑职务，并被开除出党，这使匈牙利变成了一个火药桶，赫鲁晓夫的“秘密报告”则为这只火药桶投入了一根划着的火柴。
赫鲁晓夫第一次见到这两个国家的共产党领导人是在1945年，并在战后多次访问过波兰，他很了解波兰和匈牙利，他认为对于苏联有利的东西对其盟友也必定有用。在1955年访问华沙期间，他试图劝说波兰人将400万公顷土地改种玉米。“我告诉你们，”当时的农业部副部长斯蒂凡·斯塔斯日维斯基（Stefan Staszewski）回忆说，波兰政治局“陷入彻底的绝望之中”。赫鲁晓夫引用他祖母种植玉米的成功经验来支撑他的观点，但并没有收到成效。赫鲁晓夫告诉农艺师和农户们说，“你们大家都有祖母”，但波兰人对他的建议可能只持保留意见。当波兰的一位农艺师抱怨说，她和她的同事在别人眼里好像什么都不懂时，赫鲁晓夫对斯塔斯日维斯基大发雷霆，但斯塔斯日维斯基跟他解释说：“你听到了吗？你听到他们正在说什么吗？这就是你看到的波兰人：他们总是认为自己什么事情都比我们懂！”
