Убийство лидера ОУН Степана Бандеры, которому после войны Верховный Суд СССР заочно вынес смертный приговор, было санкционировано ЦК КПСС и лично Хрущёвым вскоре после убийства Льва Ребета. Следует отметить, что к концу 1950-х гг. политический престиж Бандеры на Западе неуклонно падал, и он был рад любому упоминанию своего имени в советской печати. В связи с этим некоторые руководители КГБ докладывали в Кремль, что убийство Бандеры не принесёт пользы, оно героизирует его образ и приведёт к консолидации украинских националистов. Но в ЦК КПСС с этим мнением не согласились и отдали приказ провести ликвидацию. Исполнителем «акции» был утверждён уже проверенный киллер Сташинский, которого стали готовить к выполнению нового важного задания партии и правительства.

Как ни странно, но у КГБ к этому времени было мало информации о Бандере. Было лишь известно, что он ездит на «опеле», иногда по воскресеньям посещает эмигрантскую украинскую церковь, пользуется псевдонимом «Поппель» и время от времени навещает любовниц. Узнав, что Бандера должен выступать на кладбище в Роттердаме на церемонии, посвящённой памяти убитого советской разведкой Евгения Коновальца, Сташинского командировали в Нидерланды, чтобы он смог воочию увидеть свою жертву. У ворот кладбища он заметил «опель», явно принадлежавший Бандере. Во время церемонии Сташинский стоял близко к могиле, но украинские боевики из охраны не дали ему сфотографировать оратора. Однако позднее эмигрантские газеты сообщили, что это был Бандера, и Сташинский запомнил его лицо. В начале 1959 г. ему было приказано ускорить операцию. Под именем Ганса-Иоахима Будайта Сташинский четыре раза ездил в Мюнхен, выслеживая Бандеру. Он не мог установить его адреса до тех пор, пока не догадался поискать его в телефонном справочнике по псевдониму Бандеры — «Поппель».

Так он узнал нужный ему адрес — Крейтмайрштрассе, дом 7. Сташинский несколько раз пытался проникнуть в этот дом, но дверь подъезда всегда была закрыта. Чёрного хода в доме не было, а пытаться пройти в подъезд вслед за входящим жильцом было рискованно. Ему требовался ключ к замку. В следующий приезд Сташинский привёз в Мюнхен орудие убийства. Это был такой же пистолет, каким он убил Ребета, но двуствольный, причём стрелять можно было как из одного ствола, так и из обоих сразу. Вместе с пистолетом он привёз и отмычку с набором ключей, рассчитывая с её помощью проникнуть в дом Бандеры. Сташинский попробовал открыть дверь всеми ключами, но ни один из них не подошёл к замку. При попытке открыть дверь один из ключей сломался и упал в замочную скважину. Позднее его обнаружила немецкая полиция, и после заявления хозяина дома, что замок никогда не разбирали, эта находка стала важным подтверждением показаний Сташинского на суде.

Сташинский сумел сделать оттиск на одном из ключей, по которому умельцы в Карлхорсте изготовили несколько вариантов других ключей к замку. В этот приезд Сташинский увидел Бандеру возле гаража, однако рядом с ним находились посторонние люди, и убийца ретировался. Орудие убийства не понадобилось, и его пришлось выбросить в канал, предварительно выпустив смертоносный заряд в воздух.

В третий раз Сташинский прибыл в Мюнхен без оружия. Целью приезда была проверка нового набора ключей к замку подъезда. Один из четырёх ключей он смог частично повернуть в замке. После этого в соседнем магазине фирмы «Вулворт» он купил напильник и подточил бороздки, после чего ключ сработал. Он вошёл в подъезд и на двери одной из квартир на четвёртом этаже увидел табличку «Рорреl».

На второй неделе октября 1959 г. Сташинский в последний раз отправился из Берлина в Мюнхен. В чемодане у него было новое орудие убийства, защитные таблетки и ингалятор. 15 октября 1959 г. Степан Бандера, как обычно, поехал домой на обед, по пути он заехал на рынок, где сделал покупки. Он оставил автомобиль в гараже и вошёл в подъезд дома, где жил с семьёй. Прежде чем войти в дом он отпустил телохранителей, и они уехали. Примерно в час дня Сташинский увидел, как Бандера ставит машину в гараж, и вошёл в подъезд раньше жертвы. Он стал подниматься по лестнице, но услышав сверху женские голоса, понял, что не может стоять на лестнице, и начал спускаться вниз. На площадке второго этажа он остановился и нажал кнопку лифта. Женщина сверху миновала его, и в это время Бандера открыл входную дверь подъезда. Сташинский поднялся на лифте на 4-й этаж и начал медленно спускаться по лестнице. Бандера нёс в правой руке сумку с продуктами. Поднявшись на третий этаж, лидер ОУН(б) узнал Сташинского — утром этого дня он видел его в церкви (убийца следил за Бандерой несколько дней). На вопрос «Что вы здесь делаете?» Сташинский поднял оружие, завёрнутое в газету, и выстрелил из обоих стволов в лицо жертве. Уходя, он успел заметить, как Бандера осел набок на площадке. Хлопок от выстрела был еле слышен, а внимание соседей привлёк крик Бандеры. Когда соседи вышли из квартир, Сташинский уже покинул место преступления, а Бандеру, которого соседи знали под именем Стефана Поппеля, обнаружили на площадке между третьим и четвёртым этажами. Лицо у него стало покрываться тёмными пятнами. Он умер по дороге в больницу, не приходя в сознание. При осмотре тела врачи обнаружили трещину в основании черепа, полученную при падении. В качестве возможной причины падения врачи назвали паралич сердца.

Установить реальную причину смерти Бандеры помогло вмешательство правоохранительных структур — при осмотре доктор нашёл у убитого кобуру с пистолетом, о чём сообщил в криминальную полицию. Когда выяснилось, что под именем Стефана Поппеля проживал Степан Бандера, то у немецких властей возникли серьёзные сомнения относительно причин его смерти. Было проведено повторное исследование трупа. В организме Бандеры обнаружили остатки синильной кислоты, а на лице — мелкие частицы стекла от разорвавшейся ампулы с ядом. Было установлено, что смерть Бандеры наступила вследствие отравления цианистым калием.

Орудие убийства Сташинский выбросил в воду, а ключ — в канализационный люк по дороге. Затем он поездом уехал во Франкфурт-на-Майне, а утром самолётом вылетел в Берлин. Чтобы запутать следствие, советской разведкой в западную печать была вброшена информация о том, что Бандеру убили по инициативе министра по делам беженцев ФРГ Теодора Оберлендера, с которым он тесно сотрудничал в годы войны. Распространялись и другие слухи, например, что Бандера покончил жизнь самоубийством, приняв яд, после того как узнал, что его ближайший соратник Матвиейко стал работать на КГБ. Однако следствие было уверено, что убийство Бандеры совершено агентами КГБ.

Заупокойная служба по Степану Бандере была совершена 20 октября 1959 г. в 9 часов утра в мюнхенской церкви Св. Иоанна Крестителя, а похороны состоялись в тот же день в 15 часов на кладбище Вальдфридхоф в Мюнхене. В день похорон, как в церкви, так и на кладбище, собралось множество людей, в том числе и делегации из разных стран.

Гроб с телом Бандеры опустили в могилу, посыпав сверху привезённой с Украины землёй и окропив водой из Чёрного моря. На могилу лидера ОУН(б) было возложено около 250 венков. Украинское националистическое движение на похоронах представляли ветераны ОУН Ярослав Стецько и Михаил Кравцив, литераторы Иван Багряный и Феодосии Осьмачка, профессора Александр Оглоблин и Иван Вовчук, бывший командир УПА Николай Фриз, митрополит УАПЦ в Диаспоре Никанор (Абрамович), генерал Николай Капустянский, а также Дмитрий Донцов, Николай Ливицкий и многие другие.