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