После прихода к власти в Германии нацистов стали укрепляться контакты между нацистскими вождями и руководителями ОУН. Коновалец писал своему духовному пастырю Андрею Шептицкому: «Всё идёт хорошо. Счастливое начало 1933 г. создало условия, при которых наша освободительная акция набирает всё большие обороты и силы. Время проверило нашу дружбу и сотрудничество с немцами, а проверив, показало, что, несмотря на многократные соблазны примириться с поляками, мы выбрали единственно правильную ориентацию. Этим мы обязаны исключительно Вашему Превосходительству».
Активизация ОУН вызвала озабоченность руководства СССР и его разведки. Эта озабоченность усилилась после 21 октября 1933 г., когда активист ОУН Николай Лемик по приказу провода украинских националистов убил во Львове секретаря советского консульства СССР, а по совместительству резидента ОГПУ Андрея Майлова, отомстив, таким образом, «за голод 1932–1933 гг. на территории Украины». После этого убийства председатель ОГПУ Менжинский приказал разработать план действий по нейтрализации террористических акций украинских националистов.
План был разработан, и для его реализации в числе прочих был привлечён проверенный агент ОГПУ Лебедь, ранее внедрённый в подпольную военную организацию украинских националистов. Таким агентом был Василий Владимирович Хомяк (Лебедем он стал в СССР, уже после вербовки). Хомяк родился в 1899 г. в Галичине. В Первую мировую войну вместе с Коновальцем он воевал против России на Юго-Западном фронте в составе корпуса Сечевых стрельцов Австро-венгерской армии. В 1915 г. попал в русский плен и до 1918 г. находился в лагере военнопленных вместе с Коновальцем. В Гражданскую войну стал заместителем Коновальца и командовал пехотной дивизией, сражавшейся против частей Красной армии на Украине. После отступления Коновальца в Польшу в 1920 г. Лебедь был направлен им на Украину для организации подпольной сети. Он попал в поле зрения органов ВЧК, его арестовали и поставили перед выбором — работать на ВЧК или умереть. Лебедь стал ключевой фигурой в борьбе с националистическим подпольем и бандитизмом на Украине. Его репутация в националистических кругах за рубежом была высокой. В конце 20-х — начале 30-х гг., убедившись в преданности Лебедя, чекисты разрешили ему выезжать на Запад по нелегальным каналам.
Официально Лебедь работал финансистом в строительном тресте в Харькове. По разработанной чекистами легенде он, будучи руководителем националистического подполья на Украине, спасаясь от ареста, якобы некоторое время скрывался, а потом по фальшивым документам устроился на советский грузовой корабль. В начале августа 1933 г. Лебедь под фамилией Хомяк оказался в одном из портов Бельгии, где встретился с Евгением Коновальцем и другими руководителями ОУН. С их помощью он легализировался и больше года находился за границей. В октябре 1934 г. через Финляндию он вернулся на Украину и доложил своим руководителям, что Коновалец вынашивает планы захвата Украины в будущей войне. От Коновальца Лебедь получил информацию о командировке в США пятерых боевиков во главе с Мишугой для убийства наркома иностранных дел СССР М. Литвинова. По информации Лебедя террористы были арестованы.
Во время «командировки» Лебедь встречался в Берлине с предшественником адмирала Вильгельма Канариса — руководителем германской разведывательной службы и узнал от него, что Коновалец дважды встречался с Гитлером, который предложил, чтобы несколько сторонников Коновальца прошли курс обучения в нацистской партийной школе в Лейпциге.
В Москве решили при содействии Лебедя-Хомяка внедрить в ОУН кадрового сотрудника центрального аппарата НКВД. Выбор пал на 28-летнего чекиста Павла Судоплатова, родом с Украины, хорошо владеющего украинским языком.
Будущий убийца Коновальца Судоплатов Павел Анатольевич родился 7 июля 1907 г. в Мелитополе в семье украинца-мельника. В 1914–1919 гг. учился в городской школе. В июне 1919 г. ушёл из города вместе с полком Красной армии, был воспитанником полка, участвовал в боях. С 1921 г. служил на канцелярских должностях в Особом отделе, затем в губернском отделе ГПУ. С 1922 г. служил в погранвойсках, с 1923 г. — на комсомольской работе. В 1925 г. направлен на работу в ГПУ и через два года стал оперативным работником. В 1928–1930 гг. учился на рабфаке ГПУ. С 1932 г. — сотрудник центрального аппарата ОПТУ, с 1933 г. — в Иностранном отделе ОГПУ, в отделении, отвечавшем за оперативное наблюдение и борьбу с украинской эмиграцией на Западе. В 30-е гг. занимал должность заместителя начальника Иностранного отдела НКВД. Являлся организатором убийства Льва Троцкого.