Сразу же после смерти Сталина начались реабилитация и освобождение отдельных людей. Видимо, первым из них был киносценарист А. Я. Каплер, арестованный в годы войны за связь с дочерью Сталина Светланой Аллилуевой. Сталин не желал этого брака. Каплер был освобожден 6 марта 1953 года. Еще через несколько дней освободили и жену Молотова Полину Жемчужину. День похорон Сталина 9 марта совпал с днем рождения Молотова. Спускаясь с трибуны Мавзолея, Хрущев и Маленков все же поздравили его с днем рождения и спросили, что бы он хотел получить в подарок? «Верните Полину», – сухо сказал Молотов и прошел мимо. Просьбу немедленно передали Берии. Последний, впрочем, и сам понимал, что неразумно держать жену Молотова в заключении. Жемчужина в этот момент была уже в Москве. В 1949 году ее приговорили к нескольким годам ссылки. Но в январе 1953 года она была включена в число участников «сионистского заговора» вместе с группой еврейских врачей и уже покойным к тому времени Михоэлсом. Ее начали допрашивать с применением пыток. Допросы прекратились только 1 или 2 марта. А 9 или 10 марта ее вызвали в кабинет к Берии. Она не знала о смерти Сталина и готовилась к худшему. Но Берия неожиданно вышел из-за стола, обнял свою гостью и воскликнул: «Полина! Ты честная коммунистка!» Жемчужина упала на пол, потеряв сознание. Но ее быстро привели в чувство, дали немного отдохнуть и переодеться и отвезли на дачу к Молотову – весьма необычный подарок к уже прошедшему дню рождения.
Молотов поддержал Хрущева и Маленкова, когда они, сохраняя все меры предосторожности, обсуждали с другими членами руководства вопрос об аресте Берии. На следующий год Молотов принял сторону Хрущева и Булганина, когда на одном из Пленумов ЦК против Маленкова были выдвинуты различные обвинения, и, в частности, в плохой работе по руководству сельским хозяйством. В последние годы при Сталине именно Маленков отвечал в Политбюро за состояние дел в сельском хозяйстве. Молотов обвинил Маленкова также в недооценке развития тяжелой индустрии. В результате Маленков был освобожден от обязанностей Председателя Совета Министров СССР, а на его пост был назначен Н. А. Булганин. Однако согласие между Молотовым и Хрущевым продолжалось недолго. Они слишком отличались друг от друга и по взглядам и по стилю работы.
Уже к концу 1954 года влияние Хрущева в новом составе руководства страной и партией становится преобладающим. Изменился не только стиль, но и содержание руководства; в Президиуме ЦК КПСС постоянно шло обсуждение множества новых инициатив и предложений. При этом руководящая роль Хрущева проявилась при проведении не только внутренней, но и внешней политики СССР, что особенно раздражало Молотова, который все еще оставался не только членом Президиума ЦК КПСС, но и министром иностранных дел. Уже при обсуждении вопроса об освоении целинных земель Молотов и Ворошилов высказали ряд возражений. Они критиковали проект постановления о новом порядке планирования в сельском хозяйстве. Молотов был также против безоговорочной «реабилитации» Иосипа Броз Тито, который оставался для него если не «фашистом», то «ревизионистом». Поэтому предварительные переговоры о нормализации отношений с Югославией проводились помимо МИДа, и Молотов не принял участия в поездке Хрущева и Булганина в Югославию. Молотов во многом мешал нормализации отношений с Японией и особенно заключению государственного договора с Австрией. Предполагалось объявить Австрию нейтральной страной, гарантировать ее нейтралитет специальным соглашением великих держав. Однако на значительной части Австрии, включая Вену, еще находились советские войска, и Молотов считал, что, уходя из Австрии, СССР делает слишком большую уступку «империалистам». В своих воспоминаниях лидер австрийских социал-демократов и будущий канцлер Австрии Бруно Крайский писал, насколько трудными были переговоры. По его словам, во время одной из встреч на переговорах Молотов повторил австрийским лидерам: «Обдумайте проект договора еще раз. Мы дадим вам всю власть в стране, мы отзовем советские войска и демонтируем все советское управление. Вы станете полностью свободными и суверенными. Но мы хотим только в одной части страны зафиксировать свое присутствие» (Цит. по: Der Spiegel. 1986. N 36. S. 149—150.). В Австрии находились в 1954 году советские войска численностью в 46 тысяч человек. Молотов предлагал вывести из страны 41 тысячу и оставить там 5 тысяч. Были, конечно, и другие проблемы, и если бы решающее слово принадлежало Молотову, то в Австрии и сегодня, вероятно, находились бы советские войска. На уступки пошли Хрущев и Булганин, и Молотов должен был отступить. Не участвовал он и в поездке Хрущева и Булганина в Индию и Бирму в 1955 году. Консервативная позиция Молотова во внешней политике была подвергнута критике на июльском Пленуме ЦК в 1955 году.
Была поставлена под сомнение и его роль как теоретика. Выступая на одной из сессий Верховного Совета СССР, Молотов сказал, что в нашей стране построены «основы социалистического общества». Это высказывание вызвало возражения у других членов ЦК, которые утверждали, что «основы социализма» были построены в СССР еще в начале 30-х годов, а в начале 50-х уже построено и само социалистическое общество. Хотя, в сущности, Молотов был более прав, чем его оппоненты, он проиграл в этом догматическом споре и вынужден был публично признать свою ошибку. В журнале «Коммунист» было опубликовано его письмо в редакцию, в котором он заявлял:
«…Считаю свою формулировку по вопросу о построении социалистического общества в СССР, данную на сессии Верховного Совета СССР 8 февраля 1955 года, из которой можно сделать вывод, что в Советском Союзе построены лишь основы социалистического общества, теоретически ошибочной и политически вредной»
(Коммунист. 1955. № 14. С. 127—128.).
Уже в 1953—1955 годах в Советском Союзе было реабилитировано около десяти тысяч человек, главным образом партийных и советских работников, о восстановлении честного имени которых просили достаточно влиятельные люди. Но Молотов после освобождения своей жены скорее противился, чем способствовал новым реабилитациям. Многие заявления шли из бесчисленных лагерей на его имя. Написал Молотову свою просьбу о реабилитации и бывший видный работник МИДа Е. А. Гнедин. Но он получил быстрый и решительный отказ. В своих воспоминаниях Гнедин писал:
«…Отказ в реабилитации, мотивированный с бесстыдством худших сталинских времен, был ответом на заявление, адресованное мною Молотову. В письме прокуратуры имелось на это точное указание. Адвокат, с которым советовалась моя жена, сказал, что было ошибкой обращаться к Молотову, хотя мы одновременно обратились в различные инстанции. К Молотову не следовало обращаться, потому что в 1953 году именно он был еще способен предложить генеральному прокурору отказать мне в реабилитации. Молотов, казалось, не был исполнителем чужой воли. Разве что тень диктатора благословила Молотова и Руденко на новые беззакония»
(Гнедин Е. Выход из лабиринта. Нью-Йорк, 1982. С. 112.).
XX съезд КПСС и закрытый доклад Хрущева на этом съезде «О культе личности и его последствиях» привели к еще большему расхождению между Хрущевым и Молотовым, которого поддержали на этот раз и такие люди, как Маленков, Каганович и Ворошилов. Д. Т. Шепилов вспоминает о неожиданном звонке, прозвучавшем в его кабинете главного редактора «Правды» после XX съезда: