1956年3月12日，正在莫斯科治療肺病的波蘭共產黨領導人波萊斯瓦夫．貝魯特讀到赫魯曉夫批評史太林的秘密報告時，突然心臟病發逝世，導致波蘭國內反蘇、反共的情緒日漸升溫。為緩和波蘭的反蘇情緒，赫魯曉夫於3月下旬來到華沙參加了貝魯特的葬禮，並安撫波蘭政府。同年6月28日，位於波蘭中西部大波蘭地區瓦爾塔河沿岸的全國第五大城市波茲南，發生大規模罷工和遊行，示威者打出「我們要麵包」的標語，要求波蘭當局提升工人工資和減少稅收。遊行最終演變為騷亂。翌日，波蘭政府派出裝甲部隊鎮壓。據官方統計，事件一共造成74人死亡，800人受傷，658人被拘捕。同年7月，波蘭共產黨第二屆七中全會推舉了曾因「右傾民族主義」入獄的瓦迪斯瓦夫．哥莫爾卡擔任新一屆波蘭領導人，並解除了蘇聯派來的康斯坦丁．羅科索夫斯基國防部長的職務。赫魯曉夫聞訊後立即邀請波共中央磋商，但波共以將召開八中全會為由拒絕。10月19日，赫魯曉夫突然飛抵華沙，向波共施壓，同時派遣蘇聯軍隊向華沙推進。在哥莫爾卡說服下，赫魯曉夫最終同意不使用武裝干涉，並將羅科索夫斯基調回蘇聯。11月14日，哥莫爾卡訪蘇．11月18日，雙方簽署《波蘇共同聲明》，宣告將在平等、不干涉內政、相互協商的基礎上發展兩國關係，駐波蘇軍不得以任何方式侵害波蘭的主權完整，這些軍隊的駐紮、調動、演習，應由雙方政府通過協商作出決定。此外，還將戰後劃歸蘇聯的波蘭地區內的居民送回波蘭。兩國的緊張關係才告緩和。

另一方面，1955年3月初在匈牙利，在史太林一手扶植的執政勞動人民黨領導人拉科西．馬加什主導下，黨中央通過決議，指控時任政府總理的納吉．伊姆雷是「反黨、反馬克思主義的右傾機會主義者」；同年7月，撤銷了納吉黨內外的一切職務； 11月，把納吉清除出黨。然而在1956年10月23日，受赫魯曉夫秘密報告的反史太林思潮影響，布達佩斯學生舉行了規模浩大的遊行示威，藉波蘭反蘇新領導人哥莫爾卡上台的契機，要求匈牙利也進行類似的改革，重新任命納吉為總理，並把首都豎立的史太林雕像推倒。當天深夜，匈牙利安全部隊向示威人群開槍。翌日早晨，蘇軍的坦克已經開進布達佩斯。但蘇聯的軍事行動反而全面激化匈牙利的騷動。10月30日，赫魯曉夫在朱可夫等人的建議下，命令蘇軍撤出匈牙利。可是，匈牙利的局勢已經完全失控，憤怒的群眾襲擊了布達佩斯勞動人民產黨總部。同時納吉呼籲匈牙利退出《華沙條約》組織，直接挑戰以赫魯曉夫為首的蘇共。赫魯曉夫最終於10月31日發出命令，蘇聯軍隊再次進入匈牙利。11月4日，匈牙利反蘇的騷動被蘇軍鎮壓，騷動中有2500人死亡，13000人受傷。而納吉遭受秘密審判後，在1958年6月18日，以叛國罪之名被處決。納吉死後被草草掩埋，所葬之處更被蘇聯列為機密。直到1989年匈牙利民主化後，納吉的遺體才獲重新安葬。