Стрелявший от воздействия паров яда был в принципе застрахован, поскольку собственная его голова будет находиться на достаточном удалении. Однако в порядке предосторожности Сташинскому выдали специальные таблетки, которые не должны были допустить сужения артерий и тем самым обеспечить нормальный приток крови в мозг в случае, если он случайно вдохнет какую-то часть паров. Кроме того, ему еще вручили и специальный ингаляционный комплект.
После инструктажа по обращению с оружием Сташинский вместе с направленцем и экспертом выехал за черту Берлина. К дереву там была привязана собака. Держа оружие в руке, он нагнулся к собаке (те двое находились у него по бокам). Поднеся оружие к носу собаки на сорок пять сантиметров, Сташинский нажал на кнопку. Из отверстия вылетела струйка жидкости, и собака тут же упала, не успев даже тявкнуть, хотя и корчилась в предсмертных судорогах минуты три.
В октябре Сташинский вылетел с аэродрома Темпельхоф из Западного Берлина в Мюнхен. Оружие он упаковал в коробочку для бутербродов и вез с собой в портфеле. На случай срыва покушения никакого оружия, чтобы покончить с собой, ему не дали. Наказали только сразу же покинуть Мюнхен. Со спецслужбой связь он должен был поддерживать открытками, давая в них закодированные сообщения. Таким образом, он остался в одиночестве со своими чувствами и мыслями.
На третье утро после прибытия в Мюнхен, в 9:30, он увидел Льва Ребета, выходившего из трамвая и направлявшегося в свое бюро. Поспешив, Сташинский быстро поднялся по лестнице до второго этажа. Остановившись, он услышал шаги поднимавшегося по лестнице Ребета. Тогда Сташинский повернулся и стал спускаться по лестнице вниз, придерживаясь правой стороны. Когда Ребет оказался на несколько ступенек ниже, Богдан выхватил предварительно снятое с предохранителя оружие, быстрым движением протянул руку, выстрелил жертве в лицо и продолжил спуск по лестнице. Он услышал, как Ребет упал, но не обернулся, вышел из здания, направился к каналу Кёгльмюльбах, находившемуся в полукилометре от площади Карлсплац, и бросил в воду цилиндрик.
Возвращаясь в гостиницу, Сташинский прошел по площади Карлсплац. На этот раз он внимательно посмотрел в сторону здания редакции, около которого стояли полицейская автомашина и машина «Скорой помощи». Это было красноречивое подтверждение успеха его миссии. Придя в гостиницу, он тут же завершил все формальности по отъезду Зигфрида Дрегера. Затем направился к главному вокзалу и сел на скорый поезд, шедший во Франкфурт-на-Майне. Во Франкфурте он переночевал в гостинице «Интернациональ», а на следующее утро вылетел самолетом британской авиакомпании в Берлин. В Карлсхорсте он письменно изложил все подробности происшедшего. Ему стало известно, что украинская эмигрантская пресса сообщила о смерти Льва Ребета от «врожденной сердечной недостаточности». После случившегося на лестничной клетке тот нашел еще в себе силы проползти вверх два лестничных пролета. Умер он уже на руках одного из своих коллег.
Примерно через две недели Сташинский присутствовал на банкете, данным местным управлением КГБ частично в его честь, а отчасти по случаю какого-то советского праздника. Ему сообщили о награждении орденом, речь при этом произнес незнакомый генерал, вручивший ему ценный подарок – фотоаппарат «Контакс».
Через небольшой промежуток времени он отправился на выполнение очередного задания – обнаружить и ликвидировать Бандеру.
Описания его личности Богдан не имел. Получив сообщение, что Бандера должен произнести речь в Роттердаме на похоронах одного из убитых лидеров украинских националистов, Сташинский тут же вылетел в Голландию, чтобы поприсутствовать на погребении и увидеть Бандеру. Около ворот роттердамского кладбища он заметил припаркованный «опель», по всей видимости принадлежавший Бандере. Сташинский стоял у самой могилы, когда произносилась траурная речь. Сфотографировать говорившего не удалось, но в эмигрантской прессе позднее он прочитал, что выступал с прощальным панегириком все-таки сам Бандера. Лицо его Богдан постарался запомнить. В начале 1959 года он получил последние указания по подготовке террористического акта.
Под именем Ханса Будейта Сташинский четыре раза ездил в Мюнхен. Во время первой же поездки ему пришла в голову мысль посмотреть в телефонной книге, нет ли там фамилии Поппель – по кличке Бандеры. Такая фамилия в книге нашлась с указанием адреса – Крайтмайштрассе, дом номер 7. Несколько раз он пытался войти в дом, но входная дверь была постоянно заперта, а черного хода не имелось. Войти в дом вместе с кем-то из жителей он посчитал рискованным. Следовательно, надо было обзавестись ключом. Сделав слепок, Сташинский выехал в Москву, чтобы заодно получить и оружие. Оно было того же типа, что применялось при убийстве Ребета, но двуствольное. Стрелять можно было одним зарядом, а также дуплетом. В Мюнхен он добрался через Берлин, завернув оружие в хлопчатобумажный платок и поместив его в цилиндрическую коробочку. Ключ мастера изготовили по принципу отмычки, да еще с пятью сменными бородками.
Сташинский немедленно использовал все пять бородок ключа, но открыть дверной замок не смог. Одна из бородок при этом даже сломалась (ее обнаружила полиция после его рассказа и приобщила в качестве доказательства его причастности к убийству Бандеры). От попытки провернуть один из ключей силой и на другой бородке остались следы, позволившие затем слесарям в Карлсхорсте подогнать ключ. Несмотря на неудавшуюся попытку проникнуть в дом, Сташинский продолжал искать возможность выйти на Бандеру. Подстеречь его в гараже, пристроенном к дому, тоже не получилось. Выстрелив предварительно в воздух, он бросил оружие в тот же канал, чтобы не везти его с собой обратно.
В третий раз он выехал в Мюнхен без оружия, взяв с собой новый набор ключей. Одна из этих бородок позволила ему частично провернуть жало замка. Приобретя в ближайшем магазине напильник, он попытался спилить оставшиеся на бородке царапины. На этот раз ключ сработал. Войдя в дом, он обнаружил на четвертом этаже дверь, на которой была прикреплена табличка с надписью «Поппель». Внимательно осмотрев весь дом, включая лифт, Богдан возвратился в Берлин. Он был убежден, что действовал в доме довольно осторожно, выходил к его входной двери в темное время и поигрывал связкой ключей, будто бы сам являлся жильцом дома.
Во вторую неделю октября 1959 года Сташинский выехал в Мюнхен в четвертый раз. У него было новое оружие, а также предохранительные таблетки и тщательно изготовленные документы. В один из дней он увидел, как Бандера заезжает в гараж. Открыв ключом входную дверь, Сташинский оказался в доме раньше Бандеры. Он поднялся вверх по лестнице в надежде, что атлетически сложенный Бандера не станет пользоваться лифтом. Услышав над своей головой женские голоса, Богдан понял, что задерживаться далее не стоит, и стал спускаться вниз. На втором этаже он остановился и нажал на кнопку лифта, не зная, где находится Бандера. В этот момент мимо него прошла какая-то женщина, кабина лифта поднялась, а в проеме входной двери дома показался Бандера. Сташинскому в этой ситуации не оставалось ничего другого, как двинуться на выход. В правой руке Бандера держал сумку с продуктами, а левой пытался вынуть из замка двери застрявший ключ. Увидя подошедшего Сташинского, Бандера придержал ногой дверь, чтобы пропустить его, продолжая возиться с ключом. Взявшись левой рукой за дверь, Богдан повернулся к Бандере и спросил по-немецки:
