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