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