В Восточной Европе влияние хрущевского отступничества от Сталина имело еще более драматичные последствия. Прочитанное в контексте недавнего примирения советского лидера с Тито и его роспуска умирающего Коминформа 18 апреля, отречение Хрущева от Сталина, казалось, предполагало, что Москва теперь будет одобрительно относиться к другим «дорогам к социализму» и отвергла террор и репрессии как инструмент коммунистического контроля. Теперь, или так считалось, впервые можно будет говорить открыто. Как объяснил чешский писатель Ярослав Зайферт на Съезде писателей в Праге в апреле 1956 года, «снова и снова на этом съезде нам говорят, что писатели должны писать правду. Это означает, что в последние годы они правду не писали... Наконец-то это кончилось. Ужасы остались в прошлом».
В Чехословакии, коммунистические лидеры которой хранили молчание о своем собственном сталинском прошлом, память о терроре была еще слишком свежа, чтобы слухи из Москвы можно было перевести в политические действия.[172]
Последствия ударной волны десталинизации в соседней Польше были совсем иными. В июне польская армия была вызвана для подавления демонстраций в западном городе Познань, разгоревшихся (как и в Восточном Берлине тремя годами ранее) из-за споров о заработной плате и тарифах. Но это только усилило широкое недовольство в течение всей осени в стране, где советизация никогда не проводилась так тщательно, как в других странах, и чьи партийные лидеры пережили послевоенные чистки практически невредимыми.В октябре 1956 года, обеспокоенная перспективой потери контроля над настроениями населения, Польская объединенная рабочая партия решила отстранить советского маршала Константина Рокоссовского от должности министра обороны Польши и исключить его из Политбюро. В то же время партия избрала Владислава Гомулку на должность Первого секретаря, заменив сталинского Болеслава Берута. Это был драматический символический шаг: Гомулка был в тюрьме всего несколько лет назад и едва избежал суда. Для польской общественности он представлял «национальное» лицо польского коммунизма, и его продвижение было широко воспринято как акт скрытого неповиновения со стороны партии, вынужденной выбирать между своими национальными избирателями и высшими властями в Москве.
Действительно, советские руководители именно так это и оценивали. Хрущев, Микоян, Молотов и еще три высокопоставленных лица вылетели в Варшаву 19 октября, намереваясь заблокировать назначение Гомулки, запретить отстранение Рокоссовского и восстановить порядок в Польше. Чтобы убедиться, что их намерения были ясны, Хрущев одновременно дал указание бригаде советских танков двигаться в сторону Варшавы. Но в жарких дискуссиях с самим Гомулкой, которые частично прошли прямо на аэродроме, Хрущев пришел к выводу, что для советских интересов в Польше будет лучше согласиться с ситуацией в польской партии, чем спровоцировать обострение и почти наверняка силовое противостояние. Гомулка, в свою очередь, заверил русских, что он сможет восстановить контроль и не намерен отказываться от власти, выводя Польшу из Варшавского договора или требуя, чтобы советские войска покинули его страну.
Учитывая неравенство сил между Хрущевым и Гомулкой, успех нового польского лидера в предотвращении катастрофы для его страны был замечательным. Но Хрущев хорошо понял своего собеседника — как он объяснил Советскому Политбюро по возвращении в Москву на следующий день, советский посол в Варшаве Пономаренко «глубоко ошибся в своей оценке Гомулки». Ценой коммунистического контроля в Польше могли бы стать некоторые кадровые изменения и либерализация общественной жизни, но Гомулка был здравомыслящим партийным деятелем и не собирался отдавать власть народным массам или противникам партии. Он также был реалистом: если уж ему не удалось унять бурные польские настроения, альтернативой была только Красная Армия. Десталинизация, как оценил Гомулка, не означала, что Хрущев планировал отказаться от любого территориального влияния или политической монополии Советского Союза.