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