Перед отъездом из Москвы Сташинский получил новый, усовершенствованный пистолет, выпускавший облачко яда. Оружие было двуствольным и позволяло убрать сразу две цели — Бандеру и его телохранителя. Ищенко, полковник КГБ, который произвел на Сташинского впечатление аристократа, велел ему ехать в Восточный Берлин и ждать дальнейших распоряжений. Богдан снова поселился в квартире на Мариенштрассе и сильно запил. Приказ он получил в середине мая 1959 года: в Кремле желали убрать Бандеру как можно скорее. Деймон выдал агенту новые документы, оружие, ампулы и таблетки с противоядием, а также ключи от парадного входа в дом Бандеры. Начальство на Лубянке идеальным местом для убийства считало именно подъезд. Но если позволяла обстановка, Сташинский мог стрелять и во дворе — на свое усмотрение.
По прибытии в Мюнхен он несколько дней жил по распорядку: с утра дежурил у дома на Крайттмайрштрассе, к одиннадцати приезжал на Цеппелинштрассе, где у Бандеры был рабочий кабинет. Сташинский не раз замечал объект — как правило, в сопровождении телохранителя, — но однажды увидел, как Бандера возвращается домой один. Он проехал по улице на своем «опеле», свернул в арку и остановился, видимо, у гаражей. Сташинский вынул из кармана пистолет и пошел было к дому, но в последнюю минуту раздумал.
Чтобы не поддаться соблазну убийства, он выстрелил в землю, а потом выбросил оружие в тот же ручей, на дне которого лежал пистолет, использованный полтора года назад при устранении Ребета.
Возможно, у Богдана упал камень с души, но теперь ему пришлось ломать голову над другой задачей: как объяснить в Карлсхорсте, почему задание не выполнено. Он подозревал, что другой агент КГБ мог за ним проследить и увидеть, как он выбросил оружие в воду. Впрочем, Сташинский знал, что никто не наблюдал за ним во дворе дома на Крайттмайрштрассе, когда он передумал убивать Бандеру. И поэтому решил сказать Деймону, что заметил какого-то человека возле гаража объекта и вынужденно отступил. Для верности он подготовил для куратора доказательство того, как пытался войти в подъезд. Сташинский якобы сломал оба ключа, что ему дали, и даже какой-то собственный ключ при попытке открыть входную дверь. Сломанный ключ и должен был показать усердие агента при выполнении задания.
Подполковнику такие новости не понравились, но что он мог поделать? В Карлсхорсте не считали нужным немедленно повторять «специальное мероприятие», да и полномочий на это без одобрения Москвы не имели. В августе Сташинский отправился в Советский Союз в отпуск. Поехал на отдых и Деймон — сначала на воды в Кисловодск, а затем в Киев, чтобы обсудить обстановку на своем участке работы. Там ему сообщили, что Сташинский во время отпуска (с 12 августа до 13 сентября) не выполнил приказ сдать поддельные документы перед посещением родного села. На столь мелкий проступок в остальном дисциплинированного сотрудника можно было закрыть глаза. Вернувшись 23 сентября 1959 года в Берлин, Деймон приказал Сташинскому готовиться к новому покушению на Бандеру в Мюнхене. Ликвидатор вылетел туда 14 октября, прихватив заряженный пистолет, таблетки, ампулы и новые ключи от парадного входа в дом на Крайттмайрштрассе. Ему следовало провести в городе от семи до десяти дней — обычный срок операции — и затем вернуться в ГДР, даже если бы поездка оказалась безуспешной.
Первым «рабочим днем» Сташинского стало 15 октября. Он не рассчитывал на какой-то результат, собираясь только войти в колею слежки. Однако с утра надо было непременно выпить таблетку с противоядием и положить во внутренний карман пальто завернутое в газету оружие. Подстерегать Бандеру у дома так поздно уже не имело смысла, поэтому агент отправился к зданию на Цеппелинштрассе, где находились украинские организации. Наблюдал за ним Сташинский с моста Людвига, возле трамвайной остановки «Немецкий музей». Именно там прохожие и пассажиры трамвая могли заметить, как молодой человек лет тридцати слонялся без дела, поглядывая время от времени в сторону Цеппелинштрассе. Вначале он заметил припаркованный возле дома номер 67 автомобиль Бандеры. А уже около полудня увидел, как на улицу вышли мужчина и женщина, сели в «опель» и уехали.
Казалось, дальнейшее можно отложить на завтра. Объект был не один, поэтому убрать его не вышло бы. Тем не менее Богдан сел на трамвай и поехал обратно к дому Бандеры — хотя бы только для отчета перед кураторами, если кто-то за ним все же следил. На Крайттмайрштрассе Сташинский не увидел ни «опеля», ни его хозяина. Он подумал, что стоит остаться там еще на какое-то время — так возможному наблюдателю не покажется, что агент выслеживает цель без надлежащего рвения. Ждать он решил до часу дня. Поглядывая в нетерпении на часы, Богдан вдруг заметил подъезжающую к дому машину. Это был знакомый «опель». Бандера ехал один, без спутницы, которую агент видел часом раньше с моста Людвига.
Когда машина заехала в арку, преследователь двинулся в том же направлении. Автомобиль стоял возле открытого гаража, водитель как раз выгружал вещи из багажника. Сташинский открыл дверь парадного хода заново изготовленными в Карлсхорсте ключами. Он вошел в подъезд — идеальное с точки зрения начальства место для устранения объекта. События развивались как будто гладко — но вдруг наверху раздался женский голос. Убийца встал у лифта и подождал, пока неизвестная не пройдет мимо него к выходу. Затем он вернулся на прежнюю позицию на первой лестничной площадке (там его не заметили бы снизу). Ничто не мешало довести дело до конца. Он услышал, как открылась дверь парадного хода. Это мог быть только Бандера. Сташинский пошел вниз по лестнице, держа в правой руке газету с оружием. Он убьет новую жертву так же, как предыдущую, — когда они поравняются. Но замысел оказался не совсем удачным. Бандера возился с дверью подъезда — ключ застрял в замке. Держа сумку с овощами в правой руке, он толкал дверь ногой, а левой тщетно пытался вытянуть ключ. Богдану пришлось разыграть пантомиму завязывания шнурка в надежде на то, что лидер ОУН(б) все же справится с положением.
Убийца засомневался — возможно, и на этот раз обстановка была неподходящей, — но не отступил. Спросив, не сломался ли замок, и получив ответ «все в порядке», Сташинский поднял завернутый в газету пистолет и выстрелил ядом Бандере в лицо. Позднее он признал, что занервничал и выпустил заряды из обоих стволов. После хлопка убийца немедленно вышел из дома, закрыл дверь и повернул налево, к Эрцгиссерайштрассе, а потом направился к центру города. Он развернул газету, сунул двадцатисантиметровый аппарат в карман, вынул носовой платок и вдохнул, приложив его ко рту. И через два часа уже ехал на скором поезде во Франкфурт.
Сташинский хотел исчезнуть из Западной Германии как можно быстрее, но, когда он доехал до Франкфурта, последний самолет в Берлин уже улетел. Заказав билет на следующий день, он снял 53-й номер в отеле «Висбаден». Сегодня эту гостиницу (она и теперь на том же месте) рекламируют, упирая на расположение в десяти минутах от центра и пятнадцати — от аэропорта. Убийцу интересовал последний. Когда он наконец-то добрался туда, газетные заголовки кричали о загадочной смерти Степана Бандеры, известного соседям под именем Стефана Попеля. Таким образом Сташинский впервые убедился в успехе операции. Приехав в Восточный Берлин, он позвонил Деймону. Подполковник уже знал, что произошло, и поздравил подчиненного с отлично выполненным заданием. Они встретились в кафе «Варшава», и Богдан рассказал все в деталях.