Дни и самого Литвинова в качестве наркома иностранных дел были сочтены после Мюнхена и дискредитации политики коллективной безопасности. Молотов позднее говорил, что «были близорукие люди и в нашей стране, которые, поддавшись вульгарным антифашистским эмоциям, забыли о провокационной работе наших (западных) союзников.» Прежде всего он подразумевал Литвинова, который, как он предполагал, увлекшись химерой коллективной безопасности, сыграл на руку британским и французским «правящим кругам», которые тайно пытались подтолкнуть Гитлера к нападению на Советский Союз. В апреле 1939 года Литвинов сделал последнюю попытку воплотить систему коллективной безопасности в реальность, предложив начать переговоры с Великобританией и Францией для заключения пакта о взаимопомощи против «агрессии в Европе». В тот же самый день, однако, советский посол в Берлине позвонил во внешнеполитическое ведомство Германии и предложил начать переговоры об улучшении советско-германских отношений. Представляется, что переговоры, которые впоследствии привели к заключению нацистско-советского пакта, направлялись скорее по каналам НКВД, а не дипломатии. Литвинов, будучи евреем по национальности и проповедником системы коллективной безопасности, был очевидным препятствием на пути переговоров с Германией. 4 мая было объявлено, что Молотов заменил Литвинова на посту наркома иностранных дел. Вскоре после этой перемены заместителями наркома иностранных дел были назначены Деканозов и Лозовский, бывший руководитель Профинтерна. Хотя Литвинов, в отличие от своих бывших заместителей, пережил чистки, для искоренения оставшихся «литвиновцев» внутри комиссариата под началом Молотова была создана группа «лучших из лучших», в которой первые скрипки играли Берия и Деканозов. Молотов и Берия носили обычные костюмы, а Деканозов появлялся в форме НКВД. Один за другим сотрудники комиссариата представали перед этим «триумвиратом», пытаясь доказать, иногда безуспешно, что они никак не связаны с врагами народа.
В течение нескольких месяцев Молотов проводил параллельные переговоры по поводу заключения пактов — открыто с Великобританией и Францией, и, после несколько сдержанного начала, с Германией, но уже тайно. Начало англо-франко-советских переговоров не встретили большого энтузиазма ни в Советском Союзе, ни в Великобритании. Чемберлен отмечал в частной переписке: «У меня есть серьезные подозрения относительно истинных целей Советского Союза и глубокие сомнения по поводу его военного потенциала, даже если он честно желает и стремится помочь.» Вероятно, Сталин рассматривал переговоры с Великобританией и Францией в основном как средство оказания давления на Германию, чтобы заставить ее подписать договор, или, в качестве альтернативы, как самое удачное решение в случае, если заключение пакта с нацистской Германией окажется невозможным. Только французская сторона проявила понимание необходимости срочного заключения подобного договора, справедливо опасаясь, что, в случае провала англо-французских переговоров, Сталин пойдет на сделку с Гитлером.
НКВД разрабатывало самые изощренные «активные действия», пытаясь склонить Германию к подписанию договора. Через несколько дней после того, как 14 апреля советский посол передал предложения Министерству иностранных дел Германии, германское посольство в Лондоне получило и передало в Берлин содержание первой из серии британских дипломатических телеграмм, в которой содержался отчет о ходе переговоров с Советским Союзом. В перехваченных телеграммах, однако, имелись необъяснимые провалы и искажения. Например, указывалось, что представители Великобритании и Франции на переговорах предложили более выгодные условия и добились большего успеха, чем было на самом деле. Наименее вероятным источником информации была германская разведка. Специалисты Германии не смогли расшифровать коды британской дипломатической почты и уж наверняка не имели своего агента в Форин Оффис, который имел бы доступ к таким телеграммам. По мнению профессора Дональда Камерона Уотта, только предположение, что источником такой информации был НКВД, может быть единственной удовлетворительной гипотезой, объясняющей неожиданный и выборочный доступ германского посольства к британской диппочте в апреле 1939 года, и столь внезапное прекращение получения информации за неделю до заключения нацистско-советского пакта, а также опущения и искажения в перехваченных телеграммах. Фон дер Шуленбург, германский посол в Москве, тоже был снабжен подобной информацией, имеющей целью ускорить переговоры по двустороннему пакту.