Эти проявления любви к Сталину до крайней степени раздражали Хрущева. На приеме, состоявшемся 1 мая 1956 года сразу после военного парада и демонстрации на Красной площади, Хрущев произнес от 12 до 15 тостов. При этом он яростно атаковал Сталина. Однако, атакуя Сталина и «сталинистов», Хрущев вынужден был уделять внимание и выступлениям с другого фланга. 12 июля Президиум ЦК КПСС выразил беспокойство по поводу событий в Познани и выступлений в кружке Петефи в Будапеште. Новое руководство Польши во главе с Э. Охабом, пришедшее к власти после внезапной смерти первого секретаря ПОРП (Польской объединенной рабочей партии) Б. Берута, стало объектом критики за свое соучастие в репрессиях. На июльском пленуме ЦК ПОРП был реабилитирован бывший вождь польских коммунистов В. Гомулка, который был в свое время обвинен в пособничестве Тито, но к этому времени был уже освобожден.
Оппозиционные настроения усиливались и в Венгрии. Прибывший в Венгрию А.И. Микоян предложил первому секретарю ВПТ М. Ракоши уйти в отставку. На его место был избран Э. Герэ, который не пользовался популярностью в стране. Тем временем через австро-венгерскую границу в Венгрию проникали подпольные вооруженные группы, в том числе и те, что были связаны с прежним фашистским режимом. В стране тайно велась подготовка к вооруженному восстанию против существующего строя.
Однако вряд ли Хрущев подозревал о том, во что могут вылиться события в Польше и Венгрии. В это время он уделял первостепенное внимание сообщениям с полей страны. Лето 1956 года оказалось на редкость урожайным. Брежнев вспоминал: «В 1956 году пробил звездный час целины. Урожай в казахстанских степях был выращен богатейший, и вместо обещанных 600 миллионов республика сдала государству
Из всех же проблем внешней политики Хрущев продолжал уделять наибольшее внимание отношениям с Югославией. В сентябре 1956 года Хрущев посетил Югославию с неофициальным визитом. Встречи Хрущева с Тито были продолжены без перерыва в Крыму до 5 октября. Мичунович записал в дневнике: «Хрущев и Тито имели возможность в течение более 10 дней непрерывно беседовать без посредников, что случилось впервые в истории югославско-советских отношений».
В октябре 1956 года внимание было привлечено и к проблемам советско-японских отношений. Поскольку в 1951 году СССР отказался принять участие в подписании в Сан-Франциско мирного договора с Японией, между двумя странами сохранялось состояние войны. Отказ СССР подписать тогда договор объяснялся тем, что наша страна выражала протест против того, что вместо Китайской Народной Республики к участию в подписании были допущены представители Чан Кайши. В то же время в соответствии с мирным договором 1951 года Япония отказывалась от своих прав на Южный Сахалин и Курильские острова, которые перешли под юрисдикцию СССР с сентября 1945 года. Однако к осени 1956 года Япония заявила о своих претензиях на ряд островов Курильской гряды. Территориальные претензии Японии мешали подписать мирный договор с СССР.
К октябрю 1956 года было принято компромиссное решение: СССР уступит Японии острова Хабомаи и Шикотан (тогда его называли в СССР «Сикотан»), Япония снимет остальные территориальные претензии и обе страны подпишут договор. Это решение было сделано в духе решений, которые принимались по настоянию Хрущева в отношении Порт-Артура и Поркаллы-Удд. О том, что на указанных островах уже 11 лет живут и трудятся советские люди, видимо не задумывались.
19 октября 1956 года в Кремле была подписана советско-японская декларация, в которой говорилось: «Союз Советских Социалистических Республик, идя навстречу пожеланиям Японии и учитывая интересы японского государства, соглашается на передачу Японии островов Хабомаи и острова Сикотан с тем, однако, что фактическая передача этих островов будет произведена после заключения Мирного Договора между Союзом Советских Социалистических Республик и Японией». Декларация была подписана с советской стороны Председателем Совета Министров СССР НА. Булганиным и министром иностранных дел СССР Д.Т. Шепиловым. С японской стороны декларация была подписана министром иностранных дел Японии Ициро Хатояма, министром земледелия и лесоводства Исциро Коно и депутатом палаты представителей Японии Сюници Мацумото. (После того как Япония в 1960 году заключила «договор о безопасности» с США, советское правительство сочло себя свободным от обязательств декларации 1956 года, и вопрос о мирном договоре остался замороженным на многие десятилетия. Об этом было объявлено в памятной записке советского правительства от 27 января 1960 года. Япония же возобновила свои претензии на южную часть Курильской гряды.)