25 ноября 1938 года Указом Президиума Верховного Совета СССР Н.И. Ежов был отстранен от должности наркома внутренних дел, а на его место назначен Л.П. Берия; 1-м заместителем наркома и начальником ГУГБ становится В.Н. Меркулов. Начальником Иностранного отдела назначен В.Г. Деканозов, лично известный Л.П. Берии и ранее работавший председателем Госплана Грузинской ССР. Заместителем начальника отдела назначается П.М. Фитин, всего три месяца назад окончивший Центральную школу НКВД СССР.

Итак, 13 мая 1939 года начальником 5-го (Иностранного) отдела ГУ ГБ был назначен П.М. Фитин. С этим человеком Павел Анатольевич будет работать против нацистской Германии и её союзников в предвоенные годы и в годы Великой Отечественной Войны.

14 июня 1939 года определилась дальнейшая судьба коммуниста Павла Судоплатова. Возможно, не без участия нового начальника Иностранного отдела. Решением партбюро НКВД СССР за притупление политической бдительности ему был объявлен выговор с занесением в личную карточку. Огромная угроза в тот период прошла буквально рядом с Судоплатовым и его семьёй, оставив, конечно, незаживающие раны на всю жизнь.

«В один из мартовских дней, — вспоминает П. Судоплатов, — неожиданно я услышал упрёк, что последнее время я бездельничаю. “Я выполняю приказ начальника отделения”, — сказал я. Берия никак не прокомментировал мои слова и приказал сопровождать его на важную, по его словам, встречу. Я полагал, что речь идёт о встрече с одним из агентов. В сентябре 1938 года я дважды сопровождал его на подобные встречи. Но машина доставила нас в Кремль. Шофёр остановил машину в тупике возле Ивановской площади. Тут я осознал, что меня примет Сталин.

На этот раз Сталин казался другим. Внимательный, спокойный, сосредоточенный.

— Товарищ Сталин, — обратился Берия к нему, — по указанию партии мы разоблачили бывшее руководство закордонной разведки НКВД и сорвали их вероломную попытку обмануть правительство. Мы вносим предложение назначить товарища Судоплатова заместителем начальника разведки НКВД, с тем чтобы помочь молодым партийным кадрам, призванным на работу в органах, справиться с выполнением задач правительства.

По словам Берии, закордонная разведка в современных условиях должна изменить плавные направления своей работы. Её основной задачей должна стать подготовка резидентур к войне в Европе и на Дальнем Востоке. Между тем, по мнению Берии, левое движение находилось в состоянии серьёзного разброда из-за попыток троцкистов подчинить его себе. Тем самым Троцкий и его сторонники бросали серьёзный вызов Советскому Союзу. Они стремились лишить СССР позиции лидера мирового коммунистического движения. Берия предложил нанести решительный удар по центру троцкистского движения за рубежом и назначить меня ответственным за проведение этих акций. Далее Берия сказал, что именно с этой целью и выдвигалась моя кандидатура на должность заместителя начальника Иностранного отдела, которым руководил Деканозов. Моя задача состояла в том, чтобы, используя все возможности НКВД, убрать Троцкого.

Далее Сталин сказан следующее:

— Троцкий, или по вашим делам “старик”, должен быть устранён в течение года, прежде чем разразится неминуемая война. Без устранения Троцкого, как показывает испанский опыт, мы не можем быть уверены, в случае нападения империалистов на Советский Союз, в поддержке наших союзников по международному коммунистическому движению. Им будет очень трудно выполнить свой интернациональный долг по дестабилизации тылов противника, развернуть партизанскую войну.

Итак, мне надлежало возглавить группу боевиков для проведения операции по ликвидации Троцкого, находившегося в это время в изгнании в Мексике. Сталин заметил при этом, что “партия никогда не забудет тех, кто в ней участвовал, и позаботится не только о них самих, но и обо всех членах их семей”.

Когда я попытался возразить, что не вполне подхожу для выполнения этого задания в Мексике, поскольку совершенно не владею испанским языком, Сталин никак не прореагировал.

Я попросил разрешения привлечь к делу ветеранов диверсионных операций в гражданской войне в Испании.

— Это ваша обязанность и партийный долг — находить и отбирать подходящих и надёжных людей, чтобы справиться с поручением партии. Вам будет оказана любая помощь и поддержка. Докладывайте непосредственно товарищу Берии, и никому больше, но помните: вся ответственность за выполнение этой акции лежит на вас. Вы лично обязаны провести всю подготовительную работу и лично отправить специальную группу из Европы в Мексику. ЦК санкционирует представлять всю отчётность по операции исключительно в рукописном виде.

После встречи со Сталиным я был немедленно назначен заместителем начальника разведки. Мне был выделен кабинет на седьмом этаже главного здания Лубянки под номером 755 — когда-то его занимал Сергей Михайлович Шпигелылас».

Тем временем Судоплатову позвонил из дома Наум Эйтингон, недавно вернувшийся из Франции.

— Павлуша, я уже десять дней как в Москве, ничего не делаю. Оперативный отдел установил за мной слежку. Уверен: мой телефон прослушивается. Пожалуйста, доложи своему начальству: если они хотят арестовать меня, пусть сразу это и делают, а не устраивают детские игры.

Судоплатов ответил Эйтингону, что ни о каких планах насчёт его ареста ему неизвестно. Он тут же предложил ему прийти к нему, затем позвонил Меркулову и доложил о состоявшемся разговоре. Тот, засмеявшись, сказал:

— Эти идиоты берут Эйтингона и его группу под наружное наблюдение, а не понимают, что имеют дело с профессионалами.

В это время по прямому проводу Судоплатову позвонил Берия и предложил: поскольку Эйтингон — подходящая кандидатура для известного мне дела, к концу дня он ждёт обоих с предложениями.

Когда появился Эйтингон, Судоплатов рассказал о замысле операции в Мексике. Ему отводилась в ней ведущая роль. Наум Исаакович согласился без малейших колебаний. Он был идеальной фигурой для того, чтобы возглавить нелегальную резидентуру в США и Мексике. Подобраться к Троцкому можно было только через нашу агентуру, осевшую в Мексике после окончания войны в Испании. Никто лучше его не знал этих людей.

Работая вместе, они стали друзьями. Приказ о ликвидации Троцкого не удивил ни того ни другого: уже больше десяти лет ОГПУ — НКВД вели против Троцкого и его организации настоящую войну. По предложению Эйтингона операция получила кодовое название «Утка». Эйтингон сразу настоял, чтобы использовать агентов из Западной Европы, Латинской Америки и США, которые никогда не участвовали ни в каких операциях против Троцкого и его сторонников. В соответствии с его планом необходимо было создать две самостоятельные группы. Первая — группа «Конь» под началом Давида Альфаро Сикейроса, мексиканского художника, лично известного Сталину, ветерана гражданской войны в Испании. Вторая — группа «Мать» под руководством Каридад Меркадер. Среди её богатых предков был вице-губернатор Кубы, а её прадед когда-то являлся испанским послом в России. Каридад ушла от своего мужа, испанского железнодорожного магната, к анархистам и бежала в Париж с четырьмя детьми в начале 1930-х годов.