Но у Богдана начались проблемы. Участники УПА приговорили его к смерти как предателя. Жить во Львове под настоящим именем было опасно — его направили в Киев. Псевдонимы менялись постоянно — Олег, Григорий Мороз, Алексей Крылов.
Тогда чекисты решили сделать из него суперагента, который уничтожит руководства УПА за рубежом — в первую очередь Бандеру и идеолога ОУН Льва Ребета. Богдану на этот момент был всего 21 год.
В Киевской школе КГБ он учит коды, немецкий и польский языки, осваивает самбо, вождение машины и стрельбу. Его натаскивали на работу оперативника: уход от наружного наблюдения, тайники, передача шифровок под видом кнопок. Богдана учат незаметно отдавать документы связным. Много времени ушло на психологическую проработку агента: надо было превратить его в идейного коммуниста, а не мстителя.
Летом 1954 года его внедряют в Польшу как агента «Тараса». Для Сташинского сочиняют биографию: мама-немка, папа-поляк, долго жил в Польше, поэтому такой плохой немецкий, решил вернуться на землю предков. Полгода он живёт в Варшаве и работает шофёром на заводе, после чего ГБ высылает его в Восточную Германию под именем Йозефа Лемана.
Здесь Богдан трудится разнорабочим и «онемечивается» — перенимает местные порядки и культуру поведения. В 1957 году он как господин Леман переезжает в Мюнхен. Его цель — Лев Ребет, идеолог ОУН и главный редактор общественно-политического журнала «Український самостійник», противник Бандеры в борьбе за лидерство.
Технология убийства уникальна. Сташинскому выдают пистолет-шприц, выстреливающий парообразной струёй цианида. Микрозаряд пороха разрывал ампулу, и её содержимое попадало на жертву. Оказываясь в лёгких, яд сжимал сосуды и вызвал остановку сердца за минуту. Сам агент также мог погибнуть, поэтому для защиты должен был выпить противоядие в момент выстрела. Опробовав такой пистолет-шприц на собаках в ближайшем лесу, Сташинский убеждается: всё работает идеально. Главный плюс — по симптомам это был скорее инфаркт. Найти цианид в крови было невозможно, он разлагался очень быстро.
В 9:30 12 октября 1957 года, после прибытия в Мюнхен, Сташинский-Леман легко выследил Ребета. Он вышел из трамвая поблизости от работы и вошёл в здание. Поднимаясь по винтовой лестнице на второй этаж, Ребет заметил, что его обогнал мужчина в сером пальто. Когда Ребет был на пару ступенек ниже, Сташинский повернулся и выстрелил в лицо. Он услышал, как Ребет упал, но не обернулся и выбежал вон. Оказавшись на улице, он зашагал в сторону Кёгльмюльбах-канала и выбросил пустой цилиндр в воду. Яда в крови не нашли, поэтому все посчитали, что Ребет умер от инфаркта.
Через два года таким же выстрелом у своей квартиры был убит и Степан Бандера.
15 октября 1959 года Степан собрался ехать домой на обед. Прибыв к себе, он отпустил охрану. Досадная ошибка. Бандера оставил автомобиль в гараже, открыл ключом дверь в подъезде дома № 7 по Крайттманштрассе. Здесь его ждал убийца. Орудие — пистолет-шприц с цианистым калием — он спрятал в газету.
Агент выстрелил жертве в лицо прямо на первом этаже возле почтовых ящиков. Всё прошло тихо, Сташинский, разумеется, убежал и затерялся в толпе через полминуты. Внимание соседей привлёк крик Бандеры, который под воздействием цианида упал на ступеньки и разбил голову. Врачи увезли Бандеру в госпиталь, но тот умер ещё в машине. Причину убийства немецкие врачи тогда так и не установили.
В Москве Сташинского награждают орденом Красного Знамени «За выполнение важного государственного задания в исключительно трудных условиях», награду он получает из рук главы КГБ Шелепина. После ликвидации Бандеры его зарплату повышают до 2500 рублей — когда вся страна получает 120 рублей.