Если бы Сталин преследовал реального Троцкого, то наваждение было бы просто необъяснимым. Однако объектом преследования стала мифическая фигура, созданная «болезненно подозрительным» воображением самого Сталина, фигура, которая все меньше и меньше имела сходство с тем Троцким, которого Сталин отправил в ссылку. По мере того как угроза, исходившая от мифического Троцкого, в глазах Сталина разрасталась все больше и больше, сила и влияние реального Троцкого постоянно падали. Ему, например, не удалось даже найти безопасной штаб-квартиры в Европе, откуда можно было заняться сплочением коммунистической оппозиции. В ноябре 1932 года он покинул Турцию в поисках нового прибежища, однако месяц спустя был вынужден вернуться. Все правительства, к которым он обращался, смогли предложить ему лишь транзитные визы. В конце концов летом 1933 года ему позволили переехать во Францию, однако он не имел права жить в Париже, подвергся целому ряду ограничений и в конце концов был изгнан из страны летом 1935 года. Из Франции Троцкий переехал в Норвегию, где опять-таки не имел возможности заниматься политической деятельностью, так что он был вынужден переехать в Мексику.
Главным организатором троцкистского движения в течение большей части тридцатых годов был не сам Троцкий, а его сын Лев Седов, переселившийся из Турции в Берлин в 1931-м и спустя два года после прихода к власти Адольфа Гитлера переехавший в Париж. Именно Седов, вплоть до своей смерти в 1938 году, издавал «Бюллетень оппозиции» и поддерживал связь с разрозненными сторонниками Троцкого. В окружении Седова, точно так же как и в окружении его отца, действовали внедренные агенты ОГПУ и НКВД. Начиная с 1934 года его ближайшим доверенным лицом и помощником был агент НКВД Марк Зборовский, он же Этьен, который помогал издавать бюллетень и поддерживать связь с немногими участниками оппозиции в России. Седов настолько доверял Зборовскому, что даже отдал тому ключ от своего почтового ящика, разрешил ему забирать корреспонденцию и хранил наиболее секретные документы и архивы Троцкого в его доме.
При Менжинском и Ягоде зарубежные операции НКВД и ОГПУ против Троцкого и его сторонников ограничивались наблюдением, внедрением агентов и дестабилизацией. При Ежове НКВД стало проводить политику ликвидации руководства троцкистского движения. В декабре 1936 года Ежов организовал «Управление особых задач», действовавшее под его личным руководством и имевшее в своем распоряжении «мобильные группы» для осуществления политических убийств за границей по приказу Сталина. Главной ареной деятельности этого управления в последующие два года стала Испания.
Советское правительство не сразу отреагировало на начало Гражданской войны в Испании в июле 1936 года, ошибочно полагая, что республиканское правительство сумеет быстро подавить восстание националистских сил под руководством генерала Франко. Однако, когда 27 августа опытный дипломат М. Розенберг прибыл в Испанию в качестве посла СССР, его сопровождала целая свита, в том числе и генерал Ян Берзин, бывший начальник военной разведки, прибывший в Испанию, чтобы возглавить советскую военную миссию. Ян Берзин был высок, седоволос и неразговорчив. Иногда, по иронии судьбы, его принимали за англичанина. Кроме него, в качестве военных советников прибыли генералы Горев и Кулик, будущий маршал Малиновский. Генералы Красной Армии участвовали в Гражданской войне под различными псевдонимами. Например, генерал Лазарь Штерн, он же генерал Эмилио Клебер, которого НКВД снабдило канадским паспортом и соответствующей «легендой», в конце 1936 года получил всемирную известность как «спаситель Мадрида»; генерал Мате Залка, он же Лукач, бывший венгерский писатель-романист, вступил в Красную Армию и, возможно, был наиболее популярным командиром в «интернациональных бригадах»; генерал Янош Галич, он же Галл, тоже родом из Венгрии и, возможно, наименее популярный командир в «интернациональных бригадах»; генерал Дмитрий Павлов, он же Пабло, возможно, самый способный из республиканских командующих танковыми войсками; и, наконец, генерал Кароль Сверчевский, он же Вальтер, офицер Красной Армии, родом из Польши, впоследствии заместитель министра обороны в польском коммунистическом правительстве времен после Второй мировой войны.
НКВД располагало не менее мощным, хотя и куда менее заметным потенциалом в самой республиканской Испании. Руководство на месте осуществлял будущий перебежчик Александр Орлов, который приехал в Испанию в сентябре 1936 года и главной задачей которого было обеспечить победу сталинизма над атакующей его марксистской ересью. В июле Исполнительный Комитет Коммунистического Интернационала (ИККИ) информировал Испанскую компартию: