Началась интенсивная подготовка Кузнецова к предстоящей миссии. Он трудился по 15–16 часов в сутки: тщательно отрабатывал легенду-биографию, по которой ему предстояло жить в чужом мундире среди врагов, прыжки с парашютом, тренировался в стрельбе из различных видов советского и немецкого личного оружия. Со специально приглашенными специалистами ГРУ Генерального штаба Красной Армии изучал организацию и структуру германских вооруженных сил, их уставы, до мельчайших подробностей вникал в порядок официальных и неофициальных взаимоотношений немецких военнослужащих, учился разбираться в наградах, званиях, знаках различия всех родов войск, полиции и СС.
Кузнецова целенаправленно готовили для работы в городе Ровно, избранном гитлеровцами в качестве столицы оккупированной Украины. Там размещались почти две с половиной сотни немецких учреждений и штабов центрального подчинения.
В конце июля 1942 года специальная подготовка Кузнецова была завершена. Он был зачислен в разведывательно-диверсионный отряд специального назначения «Победители», которым командовал Д. Н. Медведев и которому предстояло действовать в районе города Ровно.
25 августа 1942 года разведчик был выброшен с парашютом в глубоком тылу противника – в Сарненских лесах Ровенской области. В городе Ровно он появился под именем обер-лейтенанта 230-го пехотного полка 76-й пехотной дивизии Зиберта Пауля Вильгельма, кавалера двух Железных крестов и медали «За зимний поход на Восток». Хорошая профессиональная подготовка, блестящее знание немецкого языка, удивительные воля и смелость явились основой для выполнения им сложнейших разведывательно-диверсионных заданий.
Заслуга Николая Кузнецова состояла в первую очередь в том, что, он целенаправленно собирал важную для Центра разведывательную информацию. В его задачу входил, в частности, сбор сведений о передвижении воинских частей, о планах и намерениях служб гестапо и СД, о поездках высоких чинов рейха, что с успехом использовалось в борьбе с врагом. Порой разведывательной информации о противнике было так много, и она была настолько важной, что радистам отряда «Победители» приходилось передавать ее в Москву несколькими сеансами в день.
Помимо активной разведывательной работы, Кузнецов принимал непосредственное участие в ликвидации гитлеровских наместников на оккупированной территории. Так, в центре города Ровно он уничтожил руководителя главного отдела финансов при рейхскомиссариате Украины имперского советника доктора Ганса Гелля и его секретаря Винтера, которые прибыли из Берлина с заданием активизировать вывоз в Германию ценностей и продовольствия с Украины. Через месяц на том же месте он привел в исполнение народный приговор – смертельно ранил первого заместителя наместника Гитлера на Украине Эриха Коха по политическим делам генерала Пауля Даргеля. 15 ноября 1943 года вместе со своими боевыми товарищами Кузнецов осуществил одну из самых дерзких и смелых операций советской разведки в годы Великой Отечественной войны в глубоком тылу врага – похитил и доставил в отряд «Победители» генерал-майора фон Ильгена, командовавшего на Украине войсками особого назначения и широко известного жестокими карательными операциями против партизан и мирного населения. Вскоре после этого прямо в здании Верховного суда был ликвидирован жестокий палач – председатель Верховного суда на оккупированной Украине оберфюрер СС Альфред Функ, по приказу которого были расстреляны все заключенные ровенской тюрьмы.
Проведенные отважным разведчиком акты возмездия содействовали решению одной из важных задач советского командования – созданию невыносимых условий фашистским захватчикам, вероломно напавшим на нашу страну. За образцовое выполнение специальных боевых заданий в тылу немецко-фашистских захватчиков и проявленные при этом отвагу и мужество Указом Президиума Верховного Совета СССР от 26 декабря 1943 года Николай Кузнецов был награжден орденом Ленина.
15 декабря 1943 года рейхскомиссар Украины Эрих Кох отдал приказ об эвакуации из Ровно всех немецких учреждений. В Москве было принято решение о передислокации спецотряда Медведева на Запад: двигаться параллельно с гитлеровскими войсками для того, чтобы собирать и передавать в Центр информацию о передвижении немецких эшелонов, а также нарушать их коммуникации.
В начале января 1944 года Кузнецов получил новое задание – развернуть разведывательную работу в городе Львове, куда направлялись из Ровно немецкие учреждения. Одновременно для обеспечения деятельности группы Кузнецова в район Львова Медведев направил специальный отряд, оснащенный рацией.