В дивизии, где служил Судоплатов, с националистами сражались поляки, австрийцы, немцы, сербы. Война была кровопролитной и жестокой. Почти миллион человек погибли на Украине. Судоплатов, находясь уже на оперативной работе, исколесил с особыми заданиями всю Украину. Служил в Житомире, Мелитополе, Харькове. Вскоре был переведен в Москву. В управлении кадров центрального аппарата ОГПУ получил должность старшего инспектора, который курировал перемещения по службе и новые назначения в Иностранном отделе, как называлась тогда закордонная разведка. Быстро и сам стал разведчиком, пройдя все ступени этой службы. Говорили, что у него была удивительная способность угадывать чужие мысли, что позволяло принимать быстрые и правильные решения в любой ситуации. Начальство быстро отметило молодого сотрудника с такими редкими возможностями. Поступило предложение: стать разведчиком-нелегалом.
Умному человеку непросто было принять такое предложение. Много чего не хватало: образование – похвалиться нечем, не было опыта работы за границей, знания иностранных языков, да и жизнь на Западе была совершенно неизвестной. И все-таки он согласился. На постижение всех премудростей получил восемь месяцев: пять раз в неделю изучение польского и немецкого языков на явочных квартирах с преподавателями-иностранцами, другие инструкторы обучали владению оружием, приемами рукопашного боя, тайнописью и другим премудростям жизни разведчика-нелегала.
Порой казалось, что его кидают в омут с ледяной водой. И никогда больше не увидеть ни Родины, ни родных. Бывалые разведчики предупреждали: радости предстоит немного, а риска без благодарности – море. После восьми месяцев учебы его ждала первая зарубежная командировка.
После убийства во Львове боевиками Организации украинских националистов советского дипломата Майлова ОГПУ разработало план предотвращения в будущем подобных террористических акций. Было решено внедрить в зарубежные подразделения ОУН наших разведчиков. Таким было задание Судоплатову.
Он отправился за рубеж в сопровождении «главного представителя ОУН» на Украине Лебедя, который на самом деле много лет был тайным агентом Советов. Лебедь вместе с Коновальцем еще в годы Первой мировой войны вместе воевали в качестве офицеров австро-венгерской армии против России, а позже просидели несколько лет в лагере для военнопленных под Царицыным.
Не расстались они и в Гражданскую войну, когда Лебедь стал заместителем Коновальца и командовал пехотной дивизией, противостоявшей Красной Армии на Украине. В 1920 году Коновалец бежал в Польшу, а Лебедя оставил на родине для организации подпольной сети ОУН. Но его арестовали, и выбор у боевого товарища Коновальца остался один: умереть или работать на Советы. Предательство Лебедя осталось тайной для националистов, среди которых его авторитет оставался высоким. В случае войны России и Германии Коновалец рассчитывал, что именно Лебедь сумеет захватить власть в Киеве. В Москве знали все это, как знали и то, что Коновалец дважды встречался с Гитлером, который даже предложил сторонникам Коновальца пройти курс обучения в партийной школе в Лейпциге.
В такой ситуации и был послан на Запад Павел Судоплатов. В то время это был статный чернобровый красавец с благородной осанкой и лицом аристократа. Его могли принять за артиста, художника, поэта. И он блестяще играл эти роли, если требовала обстановка. То, что он сделал в разведке, сейчас приходится извлекать из бездны забвения, с трудом находя то, что тщательно секретилось и скрывалось. У тайн спецслужб нет срока давности. Такие люди, как Судоплатов, ежедневно рисковали жизнью, а знают о них единицы. Разве что ветераны-кадровики, да слушатели специальных разведшкол…
Лишь в 1936-м после множества перипетий и событий «на грани провала» разведчик оказался в Берлине. Вот тогда-то он и встретился наконец с Коновальцем. Встреча проходила на конспиративной квартире, которую предоставила германская спецслужба. Это было больше похоже на допрос с пристрастием, но Павел сумел настолько расположить к себе Коновальца, что тот послал его на три месяца в партийную школу в Лейпциге.
В той самой школе он и познакомился со всем руководством ОУН. Слушатели с пристрастием присматривались к «новому студенту», но в результате все обошлось, и школа стала просто кладезем информации. Да и Коновалец уже настолько доверял Судоплатову, что делился с ним всеми своими планами. Именно он рассказал с гордостью, что вся террористическая деятельность организации финансировалась абвером, что были уже в полной готовности две тысячи боевиков, которые должны были прийти с немцами на Западную Украину.
Война была на пороге, и Коновалец со своей организацией готовился воевать на стороне Германии. В 1938 году он настоял, чтобы Судоплатов вернулся в Советский Союз для координации действий подполья ОУН на Украине с ее зарубежными центрами. Немыслимыми путями, с фальшивыми документами он наконец добрался до Ленинграда.