А в мае 1959 года Сташинский с санкции ЦК КПСС предпринял первую попытку убийства Бандеры. Однако он не сумел проникнуть в дом, где проживал Бандера, — у него сломался ключ, — и он был вынужден срочно ретироваться. Вторая попытка была предпринята в октябре 1959 года и завершилась успешно. Пятнадцатого октября в подъезде дома № 7 по Крейтмайрштрассе был обнаружен труп некого Стефана Поппеля. Поначалу полиция сочла, что он умер от сердечной недостаточности. Но, когда выяснилось, что под именем Поппеля скрывался Бандера, у властей зародились сомнения. Была проведена более тщательная экспертиза, которая выявила в желудке и на лице Бандеры следы синильной кислоты.
Сташинский чувствовал себя героем. В декабре 1959 года его вызвали в Москву, где председатель КГБ Л.Н. Шелепин в торжественной обстановке вручил ему орден Красного Знамени и зачитал приказ о награждении, в котором говорилось, что награда вручается за «успешное выполнение особо важного задания правительства». Сташинскому сообщили также, что он направляется на курсы, где продолжит изучение немецкого языка и выучит английский, после чего будет на три — пять лет командирован на Запад, для выполнения аналогичных заданий. В принципе из него готовили нелегального шефа резидентуры по «мокрым» делам. «Работа вас ждет нелегкая, но почетная», — напутствовал Сташинского на церемонии награждения председатель КГБ Шелепин.
Но тут в жизни Сташинского произошел неожиданный поворот. Еще находясь в Берлине, он влюбился в восточную немку Инге Поль, которая была ярой антикоммунисткой. Несмотря на все старания начальства прекратить их связь, Сташинский и Инге в апреле 1960 года, ускользнув на время от усиленного наблюдения, обвенчались. Оказавшись перед свершившимся фактом, руководство было вынуждено устроить молодоженам медовый месяц в Сочи. Там, под влиянием жены, Сташинский существенно пересмотрел свои взгляды и стал чуть ли не большим антикоммунистом, чем Инге.
Летом 1961 года перед родами Инге выехала в Восточный Берлин. Сташинского же подозрительное начальство, несмотря на все его просьбы, держало в Москве. Но, когда в Москву пришло известие, что новорожденный сын Сташинского внезапно скончался от воспаления легких, его вынуждены были отпустить на похороны. В Берлине подавленный горем Сташинский признался жене, что является боевиком-убийцей. Это, однако, не разрушило брачный союз и не поколебало их намерения бежать на Запад. Вечером 12 августа, за день до того, как пути бегства с Востока перекрыла Берлинская стена, Сташинский и Инге, оторвавшись от наружного наблюдения, бежали в Западный Берлин.