Василий Владимирович Лебедь родился в 1899 году в Галиции. В годы Первой мировой войны он служил в украинских формированиях австро-венгерской армии, так называемых «украинских сичевых стрельцах», затем попал в русский плен и с 1915 по 1918 год просидел вместе с будущим вождем ОУН Коновальцем в лагере для военнопленных под Царицыным. В Гражданскую войну он стал заместителем Коновальца и командовал пехотной дивизией, сражавшейся против частей Красной Армии на Украине. В 1920 году, после отступления отрядов УНР в Польшу, Лебедь остался на Украине, где вскоре и был привлечен к сотрудничеству с органами ВЧК. Но когда это произошло, доподлинно неизвестно. Что касается дальнейшей судьбы Лебедя, то о ней известно немного. В годы Великой Отечественной войны он являлся сотрудником судоплатовского 4-го (диверсионного) управления НКВД, был заброшен на Украину, где командовал одним из прославленных отрядов ОМСБОНа. После войны он продолжал служить в органах госбезопасности, работая, в том числе, и под прикрытием украинского дипломата за рубежом. Умер Лебедь в 70-е годы в Киеве.
Стоит также отметить, что в украинской националистической литературе Лебедя упорно именуют Хомяком. Неизвестно, действительно ли это была его настоящая фамилия, а Лебедем он стал, когда начал работать в ВЧК, или же наоборот. Однако смело можно утверждать, что к началу 30-х годов никаких сомнений в том, что Лебедь является руководителем националистического подполья на Украине у Коновальца и других лидеров ОУН не было.
Во многом это было следствием того, что для эмигрантов Лебедь-Хомяк имел хорошо разработанную легенду, которая объясняла его широкие связи на Украине. Он якобы окончил специальные финансовые курсы в Харькове и работал там же в строительном тресте. Когда же в начале 30-х годов на Украине начались аресты, Лебедь по совету своего тестя скрылся из города, устроился с помощью знакомых моряков по фальшивым документам на советский корабль, на котором и прибыл в начале августа 1933 года в Бельгию. Здесь он встретился с Коновальцем и другими руководителями ОУН, которые достали ему документы на фамилии Найденко и Пригода. Около года он находился за границей, и сумел за это время вступить в контакты с руководителями немецкого абвера в Берлине. И именно они, помимо прочего, сообщили Лебедю о том, что Коновальца дважды принимал Гитлер, и что во время одной из встреч Гитлер предложил ему направить несколько оуновцев в нацистскую партийную школу в Лейпциге для того, чтобы они прошли там курс обучения.
В октябре 1934 года Лебедь через Финляндию возвратился на Украину в Киев и доложил своему руководству, что Коновалец рассматривает его как «своего человека» в СССР, способного провести подготовительную работу для захвата националистами власти в Киеве в случае войны, и что аналогичные расчеты строит в отношении его и немецкая разведка. Этим обстоятельством и решили воспользоваться в Москве для того, чтобы внедрить в ОУН своего сотрудника.
Перед ним ставилась та же задача, что и в других проводимых чекистами в те годы операциях по типу «Треста» — убедить эмигрантов в том, что их террористическая деятельность на Украине не имеет никаких шансов на успех, что власти немедленно разгромят небольшие очаги сопротивления и что надо держать все силы и подпольную сеть в резерве, пока не начнется война между Германией и Советским Союзом, и только в этом случае их использовать.
Эта операция началась в марте 1935 года, когда от Лебедя пришло письмо на конспиративный адрес ОУН в Финляндии. В нем он сообщал, что скоро прибудет в Хельсинки и хочет встретиться с представителями оуновского руководства. Кроме того, в своем письме Лебедь сообщал, что вместе с ним прибудет и его воспитанник, молодой активный националист, который на самом деле был сотрудником ИНО НКВД Павлом Судоплатовым. В июне 1935 года Лебедь вместе с Судоплатовым прибыли в Финляндию. Там Лебедь представил Судоплатова как Павла Грищенко, молодого поэта и своего воспитанника, вполне пригодного для работы в подполье. Выполнив эту задачу, Лебедь в августе того же года через Финляндию вернулся на Украину.
Здесь надо особо отметить, что у ИНО НКВД в это время появился еще один агент в ОУН, Кондрат Полуведько, недавно ставший главным представителем Коновальца в Финляндии. Полуведько, в период Гражданской войны получивший определенную известность в петлюровских кругах (он был украинским эсером), рано порвал с эсерами, отошел от активной политической деятельности и некоторое время работал в системе наркомпроса Украины, занимая в нем довольно видное положение. Однако, когда в начале 30-х годов украинские чекисты обратились к нему с предложением выехать за границу для работы против украинских националистов, Полуведько согласился им помочь.
Для него была разработана легенда, согласно которой он входил в одну из националистических групп, ликвидированных в начале 30-х годов, был осужден, однако сумел бежать с Соловков в Финляндию. Оказавшись в Хельсинки, Полуведько присоединился к здешним оуновцам и вскоре завоевал их полное доверие. Более того, после отъезда местного националистического лидера Ярослава Барановского в Аргентину, его даже избрали главой Украинской Громады в Финляндии. Несколько позднее он стал членом ОУН и ее представителем в Хельсинки. Его главной задачей было поддержание связи между украинскими националистами в изгнании и их подпольной организацией в Ленинграде. Эти контакты были для оуновцев чрезвычайно важными, так как именно в Ленинграде, в знаменитой библиотеке имени Салтыкова-Щедрина они прятали свои архивы. И хотя в НКВД об этом знали давно, обнаружить архивы удалось лишь после окончания Второй мировой войны, в 1949 году.
Что же касается Судоплатова, то он в конце 1935 года встретился с прибывшими в Хельсинки связными от Коновальца — Омельяном Сеник-Грибивским из Праги и Дмитром Андриевским из Брюсселя, вместе с которыми и отправился в Германию. В январе 1936 года Судоплатов прибыл в Берлин, где прожил полгода под фамилией Норберт. Здесь он встретился с лидером ОУН Коновальцем. Встреча проходила на квартире, находившейся в здании Музея этнографии и выделенной Коновальцу абвером. А вскоре Судоплатова послали на три месяца в нацистскую школу в Лейпциге, где он имел возможность познакомиться с оуновским руководством. Слушателей этой школы, естественно, интересовала личность Судоплатова, едва ли не единственного из них выходца с Советской Украины, однако никаких проблем с его «легендой» не возникло. Более того, в общении со своими «коллегами» по нацистской партийной школе Судоплатов держался абсолютно уверенно и независимо: ведь он «представлял головную часть» их подпольной организации на Украине, в то время как они являлись всего лишь эмигрантами, существовавшими на немецкие подачки. Он имел право накладывать вето на их предложения, поскольку выполнял инструкции своего «дяди» («вуйко»). Поэтому если что-то в их высказываниях ему не нравилось, достаточно было просто сказать: «Вуйко не велел!»
На руку Судоплатову было и то обстоятельство, что в это время в рядах руководителей ОУН началась борьба за власть, которая шла между двумя их главными группировками: «стариками» и «молодежью».
Первых представляли Коновалец и его заместитель и правая рука Андрей Мельник. Мельник был на год старше Коновальца и они были женаты на родных сестрах. «Молодежь» же возглавляли Степан Бандера и Роман Шухевич. Судоплатов умело воспользовался этими распрями: он сумел войти в доверие к Коновальцу, всячески прикидываясь его сторонником в борьбе против оппозиции «молодых» и, пользуясь доверием смелого, энергичного, но недалекого Коновальца, всячески разжигал неприязнь и недоверие между двумя поколениями оуновцев и их лидерами.
Помимо этого Судоплатову удалось вместе с Коновальцем совершить поездки в Париж и Вену, где он встречался лидерами «украинского правительства в изгнании» и присутствовал на переговорах о возможном развертывании сил подполья на Украине в случае начала войны.
Благодаря этому ему удалось установить, что вожди ОУН собираются в случае нападения Германии на СССР создать при поддержке немцев независимое Украинское государство. А для осуществления этих планов уже было создано две бригады общей численностью около двух тысяч человек. Кроме того, началась подготовка административных органов для областей «освобожденной» Украины.
В начале 1937 года в Москве было принято решение вывести Судоплатова на территорию СССР. Для этого его «дядя» Хомяк-Лебедь по конспиративным каналам прислал Коновальцу через Финляндию распоряжение о возвращении «племянника» на Украину, где его должны были оформить радистом на советское судно, регулярно заходившее в иностранные порты. Это якобы давало бы ему возможность поддерживать постоянную связь между подпольем ОУН на Украине и националистическими организациями за рубежом. Коновальцу идея пришлась по душе, и он согласился с возвращением Судоплатова в СССР.
Летом 1937 года Судоплатов через Брюссель направился в Финляндию, где попытался нелегально перейти границу, но был задержан финским пограничным патрулем и доставлен в Хельсинки. Там он находился около месяца, пока с помощью людей Коновальца не был освобожден, и въехал в СССР легально через Эстонию. Об успешных результатах работы Судоплатова было доложено высшему партийному руководству СССР и Украины — Сталину, первому секретарю ЦК Компартии Украины С. Косиору и Председателю ЦИК республики Г. Петровскому. А год спустя Судоплатова наградили орденом Красного Знамени.
В сентябре 1937 года Судоплатов, прикрываясь новой легендой — должностью радиста на грузовом судне — вновь выехал за границу в Бельгию. Там он встретился с ближайшими помощниками Коновальца — Дмитром Андриевским и Ярославом Барановским, которые передали ему 1000 долларов, после чего вернулся в Москву.
Тем временем в Кремле внимательно ознакомились с полученной в ходе поездки Судоплатова информацией, касающейся планов лидеров ОУН. Она не могла не вызвать серьезного беспокойства, особенно в связи с обострением международной ситуации и возможной войной между СССР и Германией. В результате было принято решение о проведении специальных операций против лидеров ОУН, и прежде всего — против Коновальца. В середине ноября 1937 года Сталин вызвал к себе наркома НКВД СССР Н. Ежова, начальника ИНО НКВД А. Слуцкого и Судоплатова, которого попросил доложить о сложившемся положении в украинской эмиграции. Доклад Судоплатова был краток: