В 1936 году Эйтингон под именем Леона Котова прибывает в Испанию в качестве заместителя резидента НКВД СССР по партизанским операциям, включая диверсии на железных дорогах. Здесь он подружился с Эрнестом Хемингуэем. В своих мемуарах Павел Анатольевич Судоплатов отмечает, что Эйтингону удалось склонить к сотрудничеству одного из лидеров фалангистов Фердинандо де Куэста. С его помощью через разведчика-нелегала Иосифа Григулевича удалось выйти на ряд чиновников в окружении Франко и принудить их к сотрудничеству с советской разведкой. Именно Котов-Эйтингон по решению республиканского правительства вывез на военно-морскую базу в Одессе весь золотой запас Испании. За эту операцию он получил орден Красного Знамени.
Находясь в Испании, Эйтингон своими глазами видел, что одной из причин поражения республиканцев стал троцкизм, поскольку в состав коалиционного правительства Народного фронта, наряду с коммунистами, входили троцкисты партии ПОУМ – рабочей партии марксистского единства. «Мы не ведем войну, мы делаем революцию» – вот один из их лозунгов. В книге «Героическая Испания» (1936) говорится: «Самую гнусную и подлую роль в Испании играет в нынешней серьезной обстановке троцкизм. Недавно реакционный французский журналист Керилис, являющийся своим человеком в кругах французской полиции, сделал на страницах „Эко де Пари“ сенсационное заявление о том, что, по неопровержимым данным французской полиции, так называемый IV Интернационал (троцкистский) теснейшим образом связан с Гестапо и используется этим последним для разлагающей работы в рядах мирового рабочего движения».
8 марта 1937 года, во время итальянского наступления на Гвадалахару, троцкисты организовывают вооруженное выступление под Валенсией, где находилось правительство Испанской республики и Генеральный штаб народной армии. 3 мая ПОУМ поднимает вооруженный мятеж в Барселоне, три дня продолжаются кровопролитные уличные бои. В конце концов ПОУМ была запрещена, а в июне всех членов ее руководства арестовала испанская республиканская служба безопасности. 20 июня 1937 года группа сотрудников НКВД под руководством резидента НКВД в Испании Орлова при участии Иосифа Григулевича похищает из тюрьмы и спустя два дня ликвидирует лидера ПОУМ Андреу Нина (операция «Николай»). Позднее за шпионаж в пользу Франко были казнены около 500 троцкистов из состава интербригад.
Для советского руководства действия троцкистов в Испании явились наглядной иллюстрацией того, что могло бы случиться в СССР, если бы война против него уже началась, и «пятая колонна» оживилась. В своих мемуарах Павел Анатольевич Судоплатов вспоминает: «Вход в здание Кремля, где работал Сталин, был мне знаком по прошлым встречам с ним. Мы поднялись по лестнице на второй этаж и пошли по длинному безлюдному коридору, устланному красным ковром… Нас с Берией пропустил тот же офицер охраны ‹…› Сталин посуровел и, чеканя слова, словно отдавая приказ, проговорил: „Троцкий должен быть устранен в течение года, прежде чем разразится неминуемая война. Без устранения Троцкого, как показывает испанский опыт, мы не можем быть уверены, в случае нападения империалистов на Советский Союз, в поддержке наших союзников по международному коммунистическому движению. Им будет очень трудно выполнить свой интернациональный долг по дестабилизации тылов противника, развернуть партизанскую войну“. ‹…› Мне надлежало возглавить группу боевиков для проведения операции по ликвидации Троцкого, находившегося в это время в изгнании в Мексике. ‹…› После встречи со Сталиным я был немедленно назначен заместителем начальника разведки. ‹…› Через десять минут по прямому проводу мне позвонил Берия и предложил: поскольку Эйтингон – подходящая кандидатура для известного мне дела, к концу дня он ждет нас обоих с предложениями. Когда появился Эйтингон, я рассказал о замысле операции в Мексике. Ему отводилась в ней ведущая роль. Он согласился без малейших колебаний. Эйтингон был идеальной фигурой для того, чтобы возглавить специальную нелегальную резидентуру в США и Мексике. Подобраться к Троцкому можно было только через нашу агентуру, осевшую в Мексике после окончания войны в Испании. Никто лучше его не знал этих людей».
Во исполнение приказа Сталина 9 июля 1939 года был доложен план агентурно-оперативных мероприятий по делу «Утка», в ходе которого агент Рамон Меркадер, завербованный резидентурой НКВД в Испании, которого с Эйтингоном связывала настоящая дружба, рано утром 20 августа 1940 года в Мексике на вилле в Койокане нанес Троцкому удар ледорубом. Эйтингон, как было условлено, дожидался Меркадера снаружи виллы в своей машине с работающим двигателем. Однако в момент удара Троцкий повернулся и был только ранен. Он громко закричал, зовя на помощь. Ворвавшиеся в комнату охранники сбили Меркадера с ног. Поняв, что тому не уйти, Эйтингон был вынужден уехать. Троцкий умер на следующий день, а Эйтингон покинул Мексику, добрался до Кубы и только спустя шесть месяцев оказался в Москве.