Через десять минут по прямому проводу мне позвонил Берия и предложил: поскольку Эйтингон — подходящая кандидатура для известного мне дела, к концу дня он ждет нас обоих с предложениями. Когда появился Эйтингон, я рассказал о замысле операции в Мексике. Ему отводилась в ней ведущая роль. Он согласился без малейших колебаний. Эйтингон был идеальной фигурой для того, чтобы возглавить специальную нелегальную резидентуру в США и Мексике. Подобраться к Троцкому можно было только через нашу агентуру, осевшую в Мексике после окончания войны в Испании. Никто лучше его не знал этих людей. Работая вместе, мы стали близкими друзьями. Приказ о ликвидации Троцкого не удивил ни его, ни меня: уже больше десяти лет ОГПУ-НКВД вели против Троцкого и его организации настоящую войну».
Разговор этот происходил не позднее марта 1939 года. Во исполнение приказа Сталина 9 июля 1939 года был доложен план агентурно-оперативных мероприятий по делу «Утка», в ходе которого агент Рамон Меркадер, завербованный резидентурой НКВД в Испании, которого с Эйтингоном связывала настоящая дружба, рано утром 20 августа 1940 года в Мексике на вилле в Койокане нанес Троцкому удар ледорубом. Эйтингон, как было условлено, дожидался Меркадера снаружи виллы в своей машине с работающим двигателем. Однако в момент удара Троцкий повернулся и был только ранен. Он громко завопил, зовя на помощь. Ворвавшиеся в комнату охранники сбили Меркадера с ног. Поняв, что тому не уйти, Эйтингон был вынужден уехать. Троцкий умер на следующий день, а Эйтингон покинул Мексику, добрался до Кубы и только спустя шесть месяцев оказался в Москве.
На выполнение операции «Утка» ушло два года. Сталин высоко оценил заслуги всех участников операции и поддержал предложение Берии об их награждении высшими орденами Советского Союза. Отмечая награды 17 июня 1941 года в номере гостиницы «Москва», Эйтингон сказал Судоплатову: «То, что происходит на границе, не провокация, а война».
В своей книге «Разведка и Кремль» Павел Анатольевич Судоплатов вспоминает, что в тот же день 17 июня из Кремля вернулись народный комиссар госбезопасности Всеволод Николаевич Меркулов и начальник внешней разведки Павел Михайлович Фитин — оба чем-то встревоженные. «В тот же день, — пишет далее Судоплатов, — Берия, вызвав меня к себе, отдал приказ об организации особой группы из числа сотрудников разведки в его непосредственном подчинении. Она должна была осуществлять разведывательно-диверсионные акции в случае войны».
По предложению Судоплатова его заместителем был назначен Эйтингон, имевший опыт боевых действий в Испании и ставший связующим звеном между группой и военным командованием. «Вместе с ним мы составляли планы уничтожения складов с горючим, снабжавших горючим немецкие моторизованные танковые части, которые уже начали сосредоточиваться у наших границ», — пишет Судоплатов.
20 июня состоялся разговор Эйтингона с командующим Западным Особым военным округом генералом армии Павловым, с которым он был знаком по Испании. Однако, со слов Эйтингона, Павлова вообще не беспокоила ситуация на границе. Командующий не видел смысла в дезорганизации тыла противника и заявил, что никаких проблем не возникнет, даже если немцам удастся вначале захватить инициативу на границе, поскольку у него достаточно сил в резерве…
В оперативном подчинении Особой группы находилась отдельная мотострелковая бригада особого назначения (ОМСБОН) — спецназ НКВД. Формированием парашютно-десантного подразделения в составе ОМСБОН занималась Муза Малиновская, рекордсменка мира по прыжкам с парашютом. Вскоре она была вызвана в кабинет Эйтингона на Лубянку. Своей дочери, тоже Музе, она рассказывала, что была буквально поражена организаторскими способностями сидящего за столом майора госбезопасности. Постоянно звонил телефон — их на приставном столике стояло пять или шесть. Хозяин кабинета безошибочно снимал нужную трубку и разговаривал по-английски. Снимал другую — разговаривал по-испански, третью — по-французски…
Вскоре Муза выезжает вместе с Эйтингоном в Турцию для проведения акции в отношении немецкого посла фон Папена, который настойчиво пытался вовлечь Турцию в войну против СССР на стороне Германии. 24 февраля 1942 года в 10 часов утра на главной улице Анкары прогремел взрыв, в результате которого в 18 метрах от германского посла и его жены был буквально разорван на куски несущий взрывное устройство человек. На месте взрыва удалось обнаружить лишь висевший на дереве ботинок. По отметке на его подошве полиция вышла на гостиницу, а оттуда — на советское генконсульство, которое было немедленно оцеплено. Двое из его сотрудников (один из них Георгий Иванович Мордвинов, псевдоним «Павлов») были арестованы и предстали перед судом (в 1944 году их выпустили из тюрьмы и они вернулись в Москву). Другие участники операции разными путями покидали Турцию. Во второй группе выехала и Муза Малиновская. С Эйтингоном они вновь увиделись лишь через полгода и стали мужем и женой.