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