Działania Konowalca zaniepokoiły Stalina. W listopadzie 1937 r. Sudopłatow został wezwany w towarzystwie samego ludowego komisarza spraw wewnętrznych Nikołaja Jeżowa na Kreml. Tam Stalin zażądał od gości, by opracowali plan, co zrobić z uciążliwym pułkownikiem. Tydzień później podczas drugiego spotkania Stalin nakazał likwidację przywódcy OUN. Jednocześnie zapytał Sudopłatowa o zwyczaje pułkownika. „Konowalec ogromnie lubi cukierki czekoladowe” – odparł młody oficer NKWD. „Stalin zaproponował, abym o tym pomyślał” – wspominał.

Wkrótce sekcja techniczna NKWD zbudowała bombę ukrytą w bombonierce z czekoladkami. Po zmianie położenia bombonierki z pionowego na poziomy zapalnik czasowy się uzbrajał i pół godziny później ładunek miał eksplodować. Zadanie podrzucenia bomby otrzymał Sudopłatow. W razie niepowodzenia akcji miał rozkaz Konowalca zastrzelić, a następnie „umrzeć z godnością” – wspominał. Wiosną 1938 r. na pokładzie statku handlowego „Prawda” młody agent NKWD popłynął z Murmańska do Rotterdamu, gdzie miał umówione spotkanie z przywódcą OUN. 23 maja po południu Sudopłatow zszedł na ląd i udał się do kawiarni „Atlanta”, nieopodal dworca kolejowego.

„Zauważyłem, że Konowalec czeka na mnie przy stoliku niedaleko okna. W tym momencie był sam” – wspominał Sudopłatow. „Wręczyłem mu prezent w postaci pudełka czekoladek i powiedziałem, że muszę wracać na statek. Pudełko położyłem obok niego na stole w pozycji poziomej” – opisywał. Potem agent NKWD skręcił za róg ulicy i wszedł do sklepu odzieżowego, gdzie spokojnie wybrał i kupił płaszcz oraz kapelusz. Gdy tylko usłyszał wybuch, opuścił sklep i szybkim krokiem udał się na dworzec kolejowy, by kupić bilet na pierwszy pociąg do Paryża. Tymczasem w kawiarni „Atlanta” policja zajęła się rozszarpanym ciałem pułkownika Konowalca.