3 августа 1920 года в Праге была создана «Украинская военная организация» (УВО), костяк которой составили ветераны Корпуса сичевых стрельцов. Руководил УВО Евген Коновалец. Ближайшими его помощниками являлись — А. Мельник, Ю. Головинский, Р. Сушко, Р. Ярый.
«Украинская военная организация» развернула террористическую деятельность против польских властей на территории Западной Украины. Многие из боевиков организации погибли во время этих акций или были казнены по приговору суда. Среди части населения Западной Украины, особенно студенчества, действия боевиков находили одобрение и встречали поддержку.
Помимо УВО, в 20-е годы возникли еще две связанные с ней политические организации — «Союз украинской национальной молодежи» и «Легия украинских националистов» (эта организация возникла в результате слияния нескольких мелких групп, одной из которых был «Союз украинских фашистов»).
Зимой 1929 года на съезде в Вене УВО объединилась с «Союзом» и «Легией» в единую организацию украинских националистов — ОУН, вождем которой был избран Евген Коновалец.
В это же время начались «усиленные попытки оуновских лидеров найти союзников по антисоветской деятельности в националистических движениях в разных странах, в том числе и в Германии. Но в первую очередь лидеры ОУН старались наладить связи со своими соседями и «коллегами» — литовскими националистами и национал-шовинистами».
Встреча с лидером ОУН состоялась в начале лета 1936 года в Берлине на конспиративной квартире, расположенной в здании Музея этнографии.
Павел внутренне готовил себя к ней, проигрывал различные варианты, но Коновалец спутал все карты. Он встретил Судоплатова с распростертыми объятиями и напыщенными словами.
— Рад, рад приветствовать надружественной германской земле пана Яценко, племянника моего боевого соратника, ведущего борьбу за свободу неньки Украйны!
— Хай живе вильна Украйна! — с ходу подыграл «племянник».
Коновалец был в восторге.
«Железная легенда» Судоплатова, подкрепленная авторитетом «вуйко» (дяди), позволила ему завоевать полное доверие лидера ОУН. Павел Анатольевич писал в своих воспоминаниях:
«Мои беседы с Коновальцем становились между тем все серьезнее. В его планы входила подготовка административных органов для ряда областей Украины, которые предполагалось освободить в ближайшем будущем, причем украинские националисты должны были выступать в союзе с немцами. Я узнал, что в их распоряжении уже имеются две бригады, в общей сложности около двух тысяч человек, которые предполагалось использовать в качестве полицейских сил в Галиции (части Западной Украины, входившей тогда в Польшу) и в Германии».
В ходе доверительных бесед Судоплатовым были выявлены и другие не менее интересные факты. Была установлена тесная связь оуновцев с хорватскими националистами, участие ОУН в убийстве югославского короля Александра и министра иностранных дел Франции Луи Барту, а также финансирование террористов абвером — разведывательной и контрразведывательной службой вермахта. Кроме того, выяснилось, что внутри Организации украинских националистов идет жестокая борьба за власть, которую ведутдве группировки — «старики» и «молодежь». Первых представляли Коновалец и его заместитель А. Мельник, а «молодежь» возглавляли С. Бандера и Костарев. Причем междуусобица зашла достаточно далеко, о чем свидетельствовал тот факт, что убийство польского министра генерала Перацкого в 1934 году украинским террористом Мацейко было проведено вопреки приказу Коновальца, и стоял за этим Бандера.
Во время встреч с руководством ОУН Судоплатов, пользуясь своим положением представителя головной части подпольной украинской организации, старался убедить их в том, что террористическая деятельность на Украине не имеет никаких шансов на успех, поскольку власти немедленно разгромят небольшие очаги сопротивления. Он настаивал на том, что «надо держать наши силы и подпольную сеть в резерве, пока не начнется война между Германией и Советским Союзом, а в этом случае немедленно их использовать».
Кроме того, он не упускал подходящего момента, чтобы внести еще больший разлад в отношения между группировками «стариков» и «молодежи». Так, когда представился случай, Судоплатов передал Коновальцу слова Костарева о том, что Коновалец слишком стар, чтобы руководить организацией, и его следует использовать лишь в качестве декоративной фигуры.