В августе 1961 года бежал на Запад Богдан Сташинский. Сташинский родился в 1932 году на Западной Украине. Он хорошо знал немецкий язык, изучив его во время оккупации Украины немцами, был красив, обладал прекрасными внешними данными. В 1951 году во время обучения во Львовском университете он был завербован сотрудниками МГБ. Умелая идеологическая обработка плюс прекрасные физические качества сделали свое дело — он стал отличным боевиком-нелегалом 13-го отдела ПГУ КГБ, занимавшегося террористическими и диверсионными операциями за рубежом.
В 1957 году он был отправлен в Карлсхорст, резидентуру КГБ в Восточном Берлине, с заданием подготовить и осуществить операцию по Ликвидации Льва Ребета, главного идеолога НТС и одного из лидеров Организации украинских националистов (ОУН). Орудие убийства было изготовлено в оружейной лаборатории КГБ («Хозяйство Железного») и представляло собой устройство, стреляющее струей газа цианида. При попадании на лицо жертвы газ вызывал остановку сердца. В 13-м отделе считали, что ничего не подозревающий патологоанатом, скорее всего, напишет в заключении, что причиной смерти явилась сердечная недостаточность. Сташинский испытал действие пистолета на собаке. Он отвел ее в лес неподалеку от Карлсхорста, привязал к дереву и выстрелил. Собака забилась в конвульсиях и через несколько секунд сдохла.
Убедившись таким образом в надежности своего оружия, Сташинский приступил к выполнению операции. Он четыре раза посетил Мюнхен, где проживал Ребет, изучил маршруты, распорядок дня и место проживания будущей жертвы. Особо тщательно прорабатывались маршруты отхода из Мюнхена в Карлсхорст. Двенадцатого октября 1957 года Сташинский убил Ребета, подкараулив его вечером в подъезде собственного дома. Вскрытие трупа Ребета, проведенное немецкими врачами, констатировало смерть от сердечного приступа, на что и рассчитывали организаторы убийства.
После успешно выполненного первого задания Сташинского поздравили с успехом и вскоре ему поручили провести второй теракт. На этот раз жертвой становится Степан Андреевич Бандера, руководитель ОУН, отряды которой жестоко сражались с Красной Армией на Украине во время войны и не давали ей спокойно вздохнуть вплоть до конца сороковых годов. Бандера жил под Мюнхеном, и у него была отлично налаженная служба безопасности, что затрудняло проведение операции.
В мае 1958 года Сташинский по фальшивым документам вылетел в Роттердам, где должна была состояться поминальная служба по убитому в 1938 году сотрудником НКВД Судоплатовым известному украинскому националисту полковнику Е. Коновальцу. На кладбище Роттердама Сташинский впервые воочию увидел Бандеру.