Одной из приоритетных задач советской внешней политики в 1954-1955 гг. стала нормализация отношений с Югославией. Исключительная резкость разрыва создавала с обеих сторон особые трудности на пути к примирению. Вынужденно активизировав после разрыва с СССР экономические связи с Западом, Югославия вместе с тем сохранила монопольную власть компартии и курс на строительство социализма. Она проводила независимую внешнюю политику, дистанцируясь от блока НАТО и согласившись лишь на участие в ассоциированном с ним Балканском пакте, в который входили также Греция и Турция. Избрав стратегию на сближение с наиболее крупной и стратегически важной балканской страной, Н.С. Хрущев и его окружение исходили из того, что возвращение Югославии в сферу влияния советской политики стало бы наиболее видимым внешнеполитическим успехом СССР после смерти И.В. Сталина. Осенью 1954 г. сходит на нет антиюгославская пропаганда в советской прессе, распускаются антититовские организации югославских коммунистов-эмигрантов. 27 мая — 2 июня 1955 г. состоялась поездка в Югославию советской делегации во главе с Н.С. Хрущевым, продемонстрировавшая стремление руководства КПСС пойти на гораздо более решительное, чем предполагалось в 1953 г., сближение с режимом Тито. Первая после восстановления отношений встреча лидеров двух стран показала нежелание команды Тито (заинтересованной в экономическом сотрудничестве СССР и Югославии) отказываться от проведения независимой, внеблоковой внешней политики. Тем не менее она не охладила решимости Н.С. Хрущева готовить новые прорывы на югославском направлении. С середины 1955 г. советско-югославские связи в различных областях заметно оживились.
Контрреформы в Венгрии дали толчок формированию с осени 1955 г. внутрипартийной оппозиции, поначалу нещадно преследовавшейся. Ситуация в корне изменилась лишь после XX съезда КПСС (14-25 февраля 1956 г.), решения которого придали мощный импульс реформаторским силам в странах советского лагеря, ведь критика тех или иных сторон однопартийной системы, за которую прежде представители оппозиционно настроенной интеллигенции подвергались гонениям, вдруг получила неожиданную поддержку из Москвы. Движение с требованием коренной демократизации и десталинизации коммунистического режима достигло в это время наибольшего размаха в Польше и Венгрии.
В Польше после смерти 12 марта 1956 г. первого секретаря ЦК ПОРП Б. Берута в партии выявились два конкурирующих течения. Главные расхождения между ними касались взгляда на взаимоотношения с КПСС. Консерваторы, за которыми закрепилось в обществе определение «натолинцев» (в честь особняка в варшавском районе Натолин, где они собирались), были слепо привержены советской модели социализма, отличаясь при этом выраженными антисемитскими настроениями (в силу этого нападали на таких влиятельных деятелей предыдущего периода как Я. Берман и Р. Замбровский). Реформаторы, именовавшиеся также «пулавянами» (в честь Пулавской улицы в Варшаве, где многие проживали), требовали большей самостоятельности ПОРП от КПСС и весьма болезненно воспринимали всплеск антисемитских чувств в стране и в партии. Вплоть до октября 1956 г. преимущество было у консерваторов, пользовавшихся благосклонностью советского руководства. С подачи Н.С. Хрущева новым лидером ПОРП стал близкий «натолинцам» Э. Охаб, при котором была несколько смягчена цензура, однако сохранялся прежний курс в отношении «гомулковщины» как правонационалистического уклонизма. Тем не менее Польша стала единственной страной советского блока, где центральная печать опубликовала закрытый доклад Н.С. Хрущева о культе личности.
Нарастало брожение в среде людей науки и искусства. Писатели, художники, ученые требовали свободы самовыражения и научного поиска, не скованного догмами сталинизма. Как грибы после дождя по всей стране возникали клубы интеллигенции (самым известным стал варшавский «Клуб Кривого колеса»). Пресса обращалась к освещению злободневных проблем. Ослабление административного давления вызвало быстрое восстановление придавленных, но не исчезнувших элементов плюрализма. Начали проявлять себя и представители некоммунистической интеллигенции (светские католики, националисты, христианские демократы, социалисты и т.д.), пытавшиеся вернуться к общественной деятельности, организуя свои клубы. Власть, следуя курсу, взятому еще в 1955 г., смотрела сквозь пальцы на не всегда «благонадежные» выступления марксистских интеллектуалов, но жестко пресекала попытки немарксистской интеллигенции создать какие-либо самостоятельные организации.