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