Спустя несколько месяцев Журавлёв порекомендовал Колониста в Москву Леониду Фёдоровичу Райхману, начальнику 5‑го отделения 2‑го (секретно-политического) отдела ГУГБ НКВД СССР. Уже вскоре Райхман станет заместителем начальника 2‑го управления (контрразведка) НКГБ СССР. Вот как впоследствии он сам вспоминал о своей первой встрече с Николаем Кузнецовым: «Прошло несколько дней, и в моей квартире раздалась телефонная трель: звонил “Колонист”. В это время у меня в гостях был старый товарищ, только что вернувшийся из Германии, где работал с нелегальных позиций. Я выразительно посмотрел на него, а в трубку сказал: “Сейчас с вами будут говорить по-немецки…” Мой друг побеседовал несколько минут и, прикрыв микрофон ладонью, сказал удивленно: “Говорит как исконный берлинец!”. Позднее я узнал, что Кузнецов свободно владел пятью или шестью диалектами немецкого языка, кроме того, умел говорить, в случае надобности, по-русски с немецким акцентом. Я назначил Кузнецову свидание назавтра, и он пришел ко мне домой. Когда он только ступил на порог, я прямо-таки ахнул: настоящий ариец! Росту выше среднего, стройный, худощавый, но крепкий, блондин, нос прямой, глаза серо-голубые. Настоящий немец, но без этаких примет аристократического вырождения. И прекрасная выправка, словно у кадрового военного, и это — уральский лесовик!»
Кузнецов был зачислен в органы контрразведки, получив уникальный статус: особо засекреченный спецагент с окладом содержания по ставке кадрового оперуполномоченного центрального аппарата. Согласно разработанной для него легенде, он становится инженером-испытателем Московского авиационного завода № 22 имени Горбунова, получив паспорт на имя этнического немца Рудольфа Шмидта.
«Мой товарищ Виктор Николаевич Ильин, крупный работник контрразведки, — вспоминает генерал-лейтенант Райхман, — был тоже им весьма доволен. Благодаря Ильину Кузнецов быстро “оброс” связями в театральной, в частности балетной Москве. Это было важно, поскольку многие дипломаты, в том числе установленные немецкие разведчики, весьма тяготели к актрисам, особенно к балеринам. Одно время даже всерьез обсуждался вопрос о назначении Кузнецова одним из администраторов… Большого театра».
Рудольф Шмидт активно знакомится с иностранными дипломатами, посещает светские мероприятия, выходит на друзей и любовниц дипломатов. При его участии в квартире военно-морского атташе посольства Германии в Москве фрегаттен-капитана Норберта фон Баумбаха (Norbert von Baumbach) был вскрыт сейф и пересняты секретные документы. Шмидт принимает непосредственное участие в перехватах дипломатической почты, входит в окружение военного атташе посольства Германии в Москве генерала кавалерии Эрнста Кёстринга (Ernst-August Köstring), наладив прослушивание его квартиры.
С началом войны Колониста передают в Особую группу при наркоме внутренних дел Лаврентии Павловиче Берия для использования по линии «Т» — террор и диверсии в тылу противника (руководитель старший майор ГБ Павел Анатольевич Судоплатов). Главная проблема состояла в том, что Колонист никогда не служил в армии. Его наставником стал сержант ГБ (что соответствовало армейскому званию лейтенанта) Фёдор Иванович Бакин, сотрудник 2‑го (украинского) отделения 2‑го отдела 4‑го управления НКВД СССР. Подготовка агента под новым псевдонимом Пух началась с полугодичного курса унтер-офицера вермахта. Благодаря своей феноменальной памяти, Пух детально изучил структуру и уставы немецкой армии, запомнил огромное количество армейских терминов и тактико-технических обозначений, звания вермахта, полиции и СС, награды и их ношение — на фронте и в тылу, научился правильно приветствовать — в пилотке, в фуражке и без головного убора, стоя и на ходу. Пух работал по 14–16 часов в сутки, проглатывая гору книг по немецкой философии, истории, искусству, труды немецких военных мыслителей. «Он буквально истерзал меня массой требований: достать планы городов, фотооткрытки, справочники, газеты, афиши, образцы проездных документов, списки членов местного самоуправления и прочее из прошлых времен, что помогло бы ему действительно выглядеть выходцем из Восточной Пруссии, — вспоминал полковник Бакин. — У него были блестящие лингвистические способности. Немецкий язык он знал безукоризненно, разбирался в диалектах, знал грамоту в исполнении готическим шрифтом. <…> Запомнился мне Николай Иванович как образец дисциплинированности, как простой русский парень и большой патриот».
Для Пуха был выбран подлинный комплект документов обер-лейтенанта, уроженца Восточной Пруссии Пауля Зиберта. На основе этих документов лейтенант ГБ Сергей Львович Окунь, зам. начальника 2‑го отделения, составил следующую легенду.
Пауль Вильгельм Зиберт родился 20 июня 1911 года в родовом поместье Шлобиттен (польск. Słobity) графа Рихарда цу Дона-Шлобиттена, потомка старинного графского рода Дона (Dohna). Граф Александр цу Дона-Шлобиттен (1661–1728) был прусским фельдмаршалом, а графиня Фридерика Шарлотта Антония Амалия цу Дона-Шлобиттен (1738–1786) была прабабушкой по мужской линии короля Дании Кристиана IX и предком многих европейских монархов. Отец Пауля служил в поместье помощником управляющего, а мать была прислугой. С началом Первой мировой войны отец был призван в армию и погиб в 1915 году. После его гибели граф Дона взял на себя заботу о семье, оплатил обучение Пауля в училище и назначил его на ту же должность помощника управляющего. В 1936 году Пауль был призван в армию, окончил двухмесячные курсы ефрейторов в Кёнигсберге и за отличную учебу был аттестован унтер-офицером. Согласно ходатайству графа Дона, имевшего генеральский чин, молодого унтера переводят в резерв, и граф назначает его своим торговым агентом. В августе 1939 года Пауль Зиберт был зачислен в 230‑й полк 76‑й пехотной дивизии, сформированной из числа прусских резервистов. В ходе французской кампании фельдфебель Пауль Зиберт отличился 14 мая 1940 года при форсировании Мааса и штурме Вердена, за что был награжден Железным крестом 2‑го класса и произведен в лейтенанты. 23 июня он был контужен и ранен разрывом гранаты. После госпиталя он был награжден нагрудным знаком «За ранение» (чёрным), уволен из армии по состоянию здоровья и вернулся в поместье Шлобиттен. С началом восточной кампании Пауля Зиберта вновь призывают, производят в обер-лейтенанты и направляют в отдел комплектования. Начальник этого отдела мог задержать выздоравливающего офицера в своём распоряжении на срок до девяти месяцев. В случае обер-лейтенанта Зиберта было решено, что его назначат на должность уполномоченного хозяйственно-экономического отдела по использованию и доставке материальных ресурсов на оккупированной местности СССР в интересах германской армии. Район, обозначенный в его командировочном удостоверении, проходил по маршруту Чернигов — Киев — Овруч — Дубно — Ровно. Таким образом, он мог находиться в Ровно — столице рейхскомиссариата Украина — не на постоянной основе, а временно бывать там по служебным делам. Необходимые документы, в том числе свидетельство о награждении Железным крестом 1‑го класса, были изготовлены сотрудником НКВД СССР Павлом Георгиевичем Громушкиным. Фотография Кузнецова в форме обер-лейтенанта была отпечатана на трофейной немецкой фотобумаге, приклеена немецким фотоклеем, все записи в документах делались только немецкими чернилами, для оттисков печатей употребляли немецкую мастику. Для окончательного усвоения воинских отношений среди офицеров вермахта, изучения употребляемого ими фронтового жаргона и многих тонкостей, связанных с пребыванием в окопах, Пух был помещен в красногорский лагерь НКВД № 27 под Москвой для немецких военнопленных. В этом лагере пленные немецкие офицеры носили форму со знаками различия, им разрешалось иметь при себе награды и личные вещи.
24 августа 1942 года поздно вечером с подмосковного аэродрома Подлипки поднялся двухмоторный Ли‑2 и взял курс на Западную Украину. 19 октября по главной улице Ровно размеренным шагом неторопливо шагал пехотный обер-лейтенант с Железным крестом 1‑го класса и знаком «За ранение» на груди, ленточкой Железного креста 2‑го класса, продернутой во вторую петлю френча, в лихо сдвинутой набекрень пилотке. На безымянном пальце левой руки поблескивал золотой перстень с монограммой на печатке. Приветствовал старших по званию четко, но с достоинством, чуть небрежно козыряя в ответ солдатам. Самоуверенный, спокойный хозяин оккупированного украинского города, само живое олицетворение победоносного вермахта.
7 февраля 1943 года Пух, устроив вместе с группой партизан из отряда Медведева «Победители» засаду на шоссе Ровно — Киев, захватил немецкий бронированный «опель». Находившийся в нем зондерфюрер граф Гаан был убит, а двое других офицеров взяты в плен. В портфеле одного из них была обнаружена карта, по которой удалось установить, что в 8 км от Винницы построен бункер Гитлера. 13 марта фюрер подписал здесь Оперативный приказ № 5, предписывающий «по окончании весенней распутицы перейти в наступление против русских… ударом из района Харькова в северном направлении». Это было прологом к последующей операции «Цитадель» на Курской дуге. Пух узнал об этой операции от самого Эриха Коха — ближайшего соратника Гитлера, гауляйтера Восточной Пруссии и рейхскомиссара Украины. Имея задание ликвидировать Коха, Пух завязал дружеские отношения с его дрессировщиком собак, а тот представил обер-лейтенанта Зиберта гауптману Бабаху, личному адъютанту Коха. Повод был основательный — невесте Зиберта фольксдойче фрейлейн Довгер грозит отправка на работу в Германию. Аудиенция у «эрцгерцога Эриха» была назначена на 31 мая. После войны Валентина Довгер вспоминала, что, готовясь к визиту, Кузнецов был абсолютно спокоен. Утром собирался, как всегда, методично и тщательно. Положил пистолет в карман кителя. Однако в ходе аудиенции каждое его движение контролировалось охраной и собаками и стрелять было бесполезно. И здесь произошло невероятное. Узнав, что Зиберт родом из Восточной Пруссии, Кох припомнил, что еще задолго до войны приезжал в поместье Шлобиттен на охоту и видел там светловолосого юношу — служащего графа Дона. Это так расположило его к сидящему напротив фронтовику, что Кох проговорился о предстоящем летнем наступлении под Курском. Информация тут же ушла в Центр.