Заместителем Фитина 10 мая 1939 года был назначен Павел Анатольевич Судоплатов, который с 1935 года находился на нелегальной работе в Германии, под легендой участника антисоветского националистического подполья на Украине был внедрен в Организацию украинских националистов (ОУН), проник в ближайшее окружение ее лидера Евгена Коновальца и 23 августа 1938 года по личному поручению Сталина ликвидировал Коновальца в Роттердаме, передав ему коробку конфет с заложенным в нее взрывным устройством.
Одновременно со своим назначением заместителем начальника внешней разведки Судоплатов получил задание возглавить операцию по ликвидации Троцкого. В своих воспоминаниях он пишет: «Вход в здание Кремля, где работал Сталин, был мне знаком по прошлым встречам с ним. Мы поднялись по лестнице на второй этаж и пошли по длинному безлюдному коридору, устланному красным ковром… Нас с Берией пропустил тот же офицер охраны <…> Сталин посуровел и, чеканя слова, словно отдавая приказ, проговорил: “Троцкий должен быть устранен в течение года, прежде чем разразится неминуемая война. Без устранения Троцкого, как показывает испанский опыт, мы не можем быть уверены, в случае нападения империалистов на Советский Союз, в поддержке наших союзников по международному коммунистическому движению. Им будет очень трудно выполнить свой интернациональный долг по дестабилизации тылов противника, развернуть партизанскую войну. У нас нет исторического опыта построения мощной индустриальной и военной державы одновременно с укреплением диктатуры пролетариата, – продолжил Сталин, и после оценки международной обстановки и предстоящей войны в Европе он перешел к вопросу, непосредственно касавшемуся меня. Мне надлежало возглавить группу боевиков для проведения операции по ликвидации Троцкого, находившегося в это время в изгнании в Мексике. <…> Через десять минут по прямому проводу мне позвонил Берия и предложил: поскольку Эйтингон – подходящая кандидатура для известного мне дела, к концу дня он ждет нас обоих с предложениями. Когда появился Эйтингон, я рассказал о замысле операции в Мексике. Ему отводилась в ней ведущая роль. Он согласился без малейших колебаний. Эйтингон был идеальной фигурой для того, чтобы возглавить специальную нелегальную резидентуру в США и Мексике. Подобраться к Троцкому можно было только через нашу агентуру, осевшую в Мексике после окончания войны в Испании. Никто лучше его не знал этих людей. Работая вместе, мы стали близкими друзьями. Приказ о ликвидации Троцкого не удивил ни его, ни меня: уже больше десяти лет ОГПУ-НКВД вели против Троцкого и его организации настоящую войну».
Во исполнение приказа Сталина 9 июля 1939 года был доложен план агентурно-оперативных мероприятий по делу «Утка», в ходе которого агент Рамон Меркадер, завербованный резидентурой НКВД в Испании, которого с Эйтингоном связывала настоящая дружба, рано утром 20 августа 1940 года в Мексике на вилле в Койокане нанес Троцкому удар ледорубом. Эйтингон, как было условлено, дожидался Меркадера снаружи виллы в своей машине с работающим двигателем. Однако в момент удара Троцкий повернулся и был только ранен. Он громко завопил, зовя на помощь. Ворвавшиеся в комнату охранники сбили Меркадера с ног. Поняв, что тому не уйти, Эйтингон был вынужден уехать. Троцкий умер на следующий день, а Эйтингон покинул Мексику, добрался до Кубы и только спустя шесть месяцев оказался в Москве.
17 июня 1941 года Берия вызвал Судоплатова и отдал приказ о создании Особой группы на базе внешней разведки для проведения диверсий в тылу у наступающих войск противника. Заместителем Судоплатова был назначен Эйтингон. Кроме того, Судоплатов обратился к Берия с предложением вернуть из мест заключения и вынужденной отставки чекистов, имеющих опыт диверсионной и партизанской работы, таких как Серебрянский, Медведев, Мордвинов и другие. Начиная с 26 июня на московском стадионе «Динамо» началось формирование войск Особой группы, которые 3 октября 1941 года были сведены в Отдельную мотострелковую бригаду особого назначения (ОМСБОН) – спецназ госбезопасности. 18 января 1942 года приказом НКВД СССР № 00145 Особая группа при наркоме внутренних дел Берия была преобразована в 4-е Управление НКВД СССР, которое также возглавил старший майор ГБ, с 1943 года генерал-лейтенант Судоплатов.