Нужно сказать, что пути Мельникова и Судоплатова уже пересекались – ведь Мельников, помимо пяти орденов Ленина и многих других наград, имел медаль «Партизану Отечественной войны I степени». В 1941 году, работая вторым секретарём Донецкого (тогда Сталинского) обкома партии, он занимался организацией подпольной работы на оккупированной территории Горловского района, используя связи с подпольщиками Енакиево, сёл Зайцево и Байрак, станции Никитовка. По предложению Мельникова секретарем Горловского подпольного горкома партии был утвержден Семён Николаевич Щетинин – в 1942 году он станет первым секретарём Сталинского подпольного обкома партии. Мельников встречался со Щетининым в ноябре 1941 года в Луганске (тогда Ворошиловграде). На обратном пути в Горловку Щетинин установил связь с людьми Судоплатова, возглавившего по линии НКВД СССР всю зафронтовую разведывательно-диверсионную работу.
С 1944 года бандеровским подпольем на Украине руководил Роман Шухевич, бывший заместитель командира специальбатальона абвера «Нахтигаль», который с 31 октября 1945 года находился в розыске (разыскное дело НКГБ Украины «Волк»). В 1946 году Шухевичу было присвоено звание генерала-хорунжего УПА. 30 мая 1947 года он объединил остатки УПА и действующее подполье ОУН(б) в единое целое и развязал беспрецедентный по своим масштабам и жестокости террор против мирного населения. Украинский историк Анатолий Чайковский приводит цитату из обращений Шухевича того времени: «ОУН має діяти так, щоб усі хто визнав радянську владу, були знищені. Не залякувати, а фізично знищувати! Не потрібно боятися, що люди прокленуть нас за жорстокість. Хай із 40 мільйонів українського населення залишиться половина – нічого страшного у цьому немає» («Не запугивать, а истреблять! Не надо бояться, что люди проклянут нас за жестокость. Пусть из 40 миллионов украинского населения останется половина – ничего ужасного в этом нет»).
Видя, что Хрущёв способен лишь подлить масла в огонь, Сталин снимает его с поста первого секретаря ЦК компартии Украины, а на его место 18 декабря 1949 года назначает Мельникова, который, будучи сам опытным подпольщиком, сразу же поднимает местные партийные и общественные организации, ставя перед ними задачу убедить население пойти на компромисс с советской властью и не участвовать в бойне. Этим путем удается выйти на некоторых родственников влиятельных участников бандеровского подполья с предложением как можно быстрее закончить войну и вернуть людей к нормальной жизни. Одним из таких ценных агентов стала «Полина», которая добровольно явилась в УМГБ по Львовской области с повинной. Поставив условием освобождение своего брата, она предложила чекистам помощь в задержании доверенного лица Шухевича – Дарины Гусяк по кличке «Нюся».
Оперативную группу во Львове возглавил лично начальник контртеррористического управления «2-Н», замминистра государственной безопасности УССР генерал-майор Виктор Александрович Дроздов, который в 1941–1943 годах работал под началом Судоплатова. 3 марта 1950 года «Нюся» была арестована. Как сообщает Дроздов в «Справке о ликвидации руководителя оуновского подполья в Западных областях УССР – Шухевича Р.И.» от 17 марта 1950 года, «при ней были выявлены пистолет “ТТ”, ампула с ядом, которую она пыталась проглотить. Во время активного допроса 3 и 4 марта с. г. “Нюся” отказалась указать место, где прячется Шухевич, и отвлекала внимание оперативных работников на территорию, где Шухевича не было. В связи с этим была разработана и проведена сложная агентурная комбинация, в результате которой стало известно, что в селе Белогорща Брюховецкого района, расположенного в предместье Львова, скрывается Шухевич и его ближайшая помощница Дидык Галина».
Операцию по захвату Шухевича утвердили Судоплатов и Дроздов. 5 марта 1950 года в 8.30 утра во время проверки дома, где предположительно находились Шухевич и Дидык, из-за деревянной перегородки на лестнице были произведены выстрелы. В это время по лестнице поднимались начальник отделения управления «2-Н» майор Ревенко и заместитель начальника УМГБ по Львовской области полковник Фокин. В возникшей перестрелке майор Ревенко был убит. В этот момент из укрытия выскочил бандит с пистолетом и гранатой и бросился вниз по ступенькам, налетев на полковника Фокина. Подбежавший Сержант Полищук, который стоял во дворе, выпустил по бандиту автоматную очередь. Труп был предъявлен для опознания сыну Шухевича Юрию, бывшей сожительнице Шухевича Екатерине Зарицкой по кличке «Монета» и еще бывшему хозяйственному референту центрального провода ОУН по имени Зиновий Благий. «Все они сразу и без всяких колебаний опознали в трупе Шухевича», – говорится в совершенно секретной записке, подписанной генерал-лейтенантом Судоплатовым и генерал-майором Дроздовым и направленной в тот же день по ВЧ министру государственной безопасности СССР генерал-полковнику Виктору Семёновичу Абакумову.