Когда арестованному Нину предъявили обвинение в предательстве, он отмел его с порога. Тогда его отправили в тюрьму города Алкала-де-Энарес, где долго допрашивали, добиваясь чистосердечного признания. Но, как с сожалением сообщал в Москву Орлов о ходе операции «Николай» (так называлась акция по ликвидации А. Нина), испанец оказался мужественнее советских коммунистов и категорически отрицал свою вину. Тогда было решено похитить Нина и «заставить исчезнуть» без суда и следствия, что и было сделано. Исполнителями этой акции были Орлов, сотрудник НКВД в Испании Иосиф Ромуальдович Григулевич (ЮЗИК) и три сопровождавших их испанца. Тело расстрелянного Нина было вывезено из тюрьмы и наспех похоронено у отметки «17 километр» на шоссе близ Алкала-де-Энареса. Кроме Нина были уничтожены бывший секретарь Льва Троцкого немец Эрвин Вольф, сын меньшевика Абрамовича Марк Рейн и многие другие.
Выполняя столь грязную и неблагодарную работу, Орлов нисколько не походил на палача. Вот как описывает первую встречу с ним боец интербригад, а потом агент НКВД Кирилл Хенкин:
«Меня поразил его ухоженный вид. Только что душ, только что бритье с одеколоном… Он был одет по-утреннему: в серых фланелевых брюках, в шелковой рубашке без галстука. На поясе — открытая замшевая кобура с пистолетом Вальтер калибр 7,65.
Мне повезло. Выслушав мои путаные объяснения: кто я, зачем, от кого, откуда приехал и почему пришел именно к нему, он не приказал охране меня пристрелить. Для порядка. Бывало и такое. Но в то утро я был парализован зрелищем завтрака, который перед носом у меня вкушал Орлов.
Лакей в белой куртке вкатил столик, снял салфетку и удалился. Орлов намазал маслом горячий тост, откусил уголок, принялся за яичницу с ветчиной, иногда отхлебывая кофе. К сливкам он не прикоснулся. Он не был, видимо, особенно голоден. Подобрав остаток желтка кусочком круассана и выпив последний глоток кофе, Орлов отодвинул столик, на котором оставалась еще булочка, масло, кувшинчик со сливками и пол-кувшинчика кофе, достал пачку «Лакки страйк», вынул сигарету и закурил».
Но в 1937 году над Орловым стали сгущаться тучи. Первой ласточкой стала полученная в августе 1937 года телеграмма от начальника ИНО НКВД A.A. Слуцкого. В ней говорилось, что секретные службы Франко и гитлеровской Германии разработали план похищения Орлова. В связи с этим Слуцкий собирается послать Орлову охрану из двенадцати человек, которая отвечала бы за его безопасность и сопровождала во всех поездках. Почуяв неладное, Орлов ответил Слуцкому, что в охране не нуждается, и одновременно набрал десяток человек личной охраны, всюду его сопровождавших. Вторым сигналом для Орлова послужило прибытие в Испанию в октябре 1937 года заместителя Слуцкого С. Шпигельгласа, организовавшего 4 сентября 1937 года в Швейцарии убийство И. Рейсса. Не имея в Испании никаких явных дел, Шпигельглас встретился с Володиным, который руководил в Мадриде мобильной группой Отдела специальных операций. Это настолько обеспокоило Орлова, что он вывез жену и дочь во Францию в Перпиньян, где снял для них виллу.