В составе партизанского отряда «Мстители» под командованием Д. Н. Медведева Кузнецову предстояло высадиться в лесах под Ровно. Этот небольшой западноукраинский город стал столицей рейхскомиссариата «Украина». Бойцы отряда Медведева знали агента по кличке «Пух» как Николая Васильевича Грачева. В Ровно же он должен был появиться как обер-лейтенант вермахта Пауль Зиберт.
Перед высадкой во вражеском тылу, последовавшей в ночь на 25 августа 1942 года, Кузнецов досконально изучил германские вооруженные силы, чтобы не попасть впросак при встречах с патрулями и беседами с офицерами ровенского гарнизона. Для этого он даже провел несколько недель в офицерском бараке лагеря немецких пленных в Красногорске, причем никто не заподозрил, что этот симпатичный пехотный обер-лейтенант в действительности русский. И Пауль Зиберт так же хорошо, как язык, освоил стрельбу из немецкого оружия. Ведь главной его задачей должно было стать осуществление террористических актов против высших чиновников германской оккупационной администрации на Украине. Использовать столь квалифицированного агента для подобных целей было равносильно тому, чтобы топить печку ассигнациями. Но летом 42-го положение Красной армии было чрезвычайно тяжелым, и руководители НКВД, нарком Л. П. Берия и его первый заместитель В. Н. Меркулов, бывший глава НКГБ, вынуждены были бросать все силы на решение сиюминутных задач. Сам Меркулов подписал приказ о направлении Кузнецова в отряд Медведева. Не исключено, что чекисты надеялись террором против высокопоставленных служащих рейхскомиссариата дезорганизовать оккупационную администрацию и спровоцировать антинемецкое восстание на Западной Украине. Однако местное население, не симпатизируя уже в ту пору немцам, к русским большевикам относилась весьма настороженно и не собиралась идти в бой за Сталина. Популярностью пользовалась Украинская Повстанческая Армия, провозгласившая борьбу как против немцев, так и против большевиков. УПА также рассматривалась как один из будущих противников отряда Медведева, наряду с немецкими войсками и подчиненной им украинской вспомогательной полицией.
При приземлении Кузнецову не повезло – потерял в болоте сапог. Но к месту сбора группы из 11 человек добрался благополучно, доложил Медведеву, как положено, руки по швам, только одна нога босая. Но это не страшно. Сапоги для него нашлись. А потом Николаю Ивановичу предстояло облачиться в другую форму – немецкого обер-лейтенанта. Но его первый визит в столицу рейхскомиссариата задержался почти на два месяца. Надо было не только разведать предварительно обстановку в городе и установить связи с агентурой. Выяснилось, что Николай Иванович обладает одной неприятной для разведчика-нелегала особенностью – разговаривает во сне, причем, естественно, на родном языке – по-русски. Многие годы Кузнецов жил один и не знал этого. Только в отряде соседи по палатке обратили внимание, что боец Грачев (про Зиберта знали только Медведев, его заместитель по разведке Александр Александрович Лукин и группа прикрытия) вскрикивает во сне. Кстати, этот факт – косвенное доказательство того, что Кузнецову не приходилось спать с женщинами. Иначе какая-нибудь из подруг указала бы ему на эту не очень симпатичную для дам привычку.