Уже в 1953–1955 годах в Советском Союзе было реабилитировано около десяти тысяч человек, главным образом партийных и советских работников, о восстановлении честного имени которых просили достаточно влиятельные люди. Но Молотов после освобождения своей жены скорее противился, чем способствовал новым реабилитациям. Многие заявления шли из бесчисленных лагерей на его имя. Написал Молотову свою просьбу о реабилитации и бывший видный работник МИДа Е. А. Гнедин. Но он получил быстрый и решительный отказ. В своих воспоминаниях Гнедин писал: «…Отказ в реабилитации, мотивированный с бесстыдством худших сталинских времен, был ответом на заявление, адресованное мною Молотову. В письме прокуратуры имелось на это точное указание. Адвокат, с которым советовалась моя жена, сказал, что было ошибкой обращаться к Молотову, хотя мы одновременно обратились в различные инстанции. К Молотову не следовало обращаться, потому что в 1953 году именно он был еще способен предложить генеральному прокурору отказать мне в реабилитации. Молотов, казалось, не был исполнителем чужой воли. Разве что тень диктатора благословила Молотова и Руденко на новые беззакония».

XX съезд КПСС и закрытый доклад Хрущева на этом съезде «О культе личности и его последствиях» привели к еще большему расхождению между Хрущевым и Молотовым, которого поддержали на этот раз и такие люди, как Маленков, Каганович и Ворошилов. Д. Т. Шепилов вспоминает о неожиданном звонке, прозвучавшем в его кабинете главного редактора «Правды» после XX съезда:

«— Товарищ Шепилов?

— Да, это я.

В голосе говорившего со мною слышалось едва сдерживаемое раздражение, он слегка заикался:

— Прекратите ругать в „Правде“ Сталина.

Я сразу понял: это был В. М. Молотов.

— Я Сталина не ругаю. Я выполняю решения XX съезда.

— Я еще раз прошу вас: прекратите ругать Сталина.

— Товарищ Молотов, — отвечаю ему. — Я могу только повторить, что сказал: я выполняю решения XX съезда. Вы недовольны? Тогда выносите вопрос на Президиум ЦК».

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

«Встреча с Молотовым проходила в атмосфере благожелательности. Беседа была искренней, временами даже сердечной, как будто речь шла о разговоре двух старых знакомых, которые долго не виделись друг с другом. Не было заметно даже следа от нашего идеологического и политического конфликта, когда именно Молотов вместе со Сталиным составлял и подписывал угрожающие письма югославскому руководству. Хотя я и не настаивал на быстрой аккредитации, Молотов обещал мне переговорить с Ворошиловым и сделать все, чтобы эта процедура произошла так скоро, как возможно… У меня, однако, осталось впечатление: хотя Молотов и был министром иностранных дел, он уже не держал всех нитей советской внешней политики.