В то же время немало советских людей, оказавшись перед выбором, кому верить — Сталину или Хрущеву, отказывались теперь верить любым руководителям страны. Доклад Хрущева усилил настроения цинизма и неверия, дал мощный импульс процессам моральной и идейной эрозии советского общества. Этим активно воспользовалась западная пропаганда, которая велась против нашей страны. Теперь западные радиоголоса вызывали больше доверия, поскольку они могли утверждать, что Хрущев, в сущности, повторил многие из обвинений, которые они выдвигали против Советской власти с первых же лет «холодной войны».
Особенно усилилось влияние западной пропаганды на социалистические страны Центральной и Юго-Восточной Европы. В радиопередачах западных «голосов» утверждалось, что руководители этих стран были поставлены у власти Сталиным, которого только что осудил Хрущев, а существовавшие там порядки мало чем отличались от тех, что были при Сталине в СССР, и теперь подверглись разносной критике советским руководством. С весны 1956 года началось брожение в этих странах, особенно в Польше и Венгрии. 28 июня 1956 года требования радикальных перемен привели к волнениям в Познани, сопровождавшимся столкновениями с полицией.
Доклад Хрущева подорвал политические позиции многих руководителей коммунистических партий земного шара, которые должны были дать объяснения рядовым коммунистам, почему они прежде прославляли Сталина, а теперь стали обвинять его во всевозможных грехах. В этих условиях некоторые из них, как, например, руководитель многочисленной Итальянской коммунистической партии Пальмиро Тольятти, старались отмежеваться от советского руководства. Тольятти ставил вопрос о «некоторых формах перерождения» советского общества. Руководство же Коммунистической партии Китая, на словах сдержанно поддержав критику Сталина, на деле было крайне недовольно докладом Хрущева.
Неоднозначная реакция международного коммунистического движения, события в Грузии и Польше, вторичный провал попыток Хрущева вернуть Югославию в социалистический лагерь в ходе визита Тито в СССР в июне 1956 года заставили руководство нашей страны искать ответы на проблемы, порожденные закрытым докладом. 30 июня 1956 года было опубликовано постановление ЦК КПСС «О преодолении культа личности и его последствий», в котором, в отличие от доклада Хрущева, не говорилось о негативных чертах характера Сталина как первопричине беззаконных репрессий. Вместо этого на первый план выступило традиционное для коммунистов всех стран объяснение: Сталин допустил отступления от марксизма-ленинизма.
Указывалось, что «Сталин повинен во многих беззакониях, которые совершались особенно в последний период его жизни». Однако это обвинение в адрес Сталина существенно смягчалось следовавшим за ним заявлением о том, что «советские люди знали Сталина как человека, который выступает всегда в защиту СССР от происков врагов, борется за дело социализма». Подводя итог этим противоречивым рассуждениям, авторы постановления делали вывод: «В этом состояла трагедия Сталина. Но все это вместе с тем затрудняло и борьбу против совершавшихся тогда беззаконий, ибо успехи строительства социализма, укрепления СССР в обстановке культа личности приписывались Сталину». В постановлении подчеркивалось, что успехи, достигнутые Советской страной, «создавали такую атмосферу, когда отдельные ошибки и недостатки казались на фоне громадных успехов менее значительными, а отрицательные последствия этих ошибок быстро возмещались колоссально нараставшими жизненными силами партии и советского общества».
Однако постановление уже не могло остановить центробежных сил, развязанных реакцией на доклад Хрущева. Резкое обострение польско-советских отношений в октябре 1956 года после избрания нового руководства польских коммунистов во главе с В. Гомулкой, восстание в Венгрии, едва не приведшее к развязыванию полномасштабной войны в Европе, показали, что следствием «десталинизации», развернутой Хрущевым, стал острый кризис в социалистическом лагере и международных отношениях. Пытаясь спасти положение, Хрущев совершил в конце октября — начале ноября 1956 года молниеносные визиты в социалистические страны. В ходе своих переговоров с Тито Хрущев был явно растерян. Он отмечал: «Люди будут говорить, что, пока был Сталин, все слушались, не было никаких потрясений, а сейчас, после того как «они» пришли к власти, Россия потерпела поражение и потеряла Венгрию».