Резкому взлету исключительно добросовестного и вдумчивого, но, как отмечалось в служебных характеристиках, несколько медлительного работника способствует приход Берии. Одновременно с Фитиным, который возглавил внешнюю разведку, Федотов выдвигается в начальники всей контрразведки страны, последовательно возглавляя 2-й отдел (4 сентября 1939 года), 3-й отдел (29 сентября 1940 года) и, наконец, 2-е Управление НКГБ СССР (Фитин, напомним, возглавил 1-е Управление НКГБ СССР). Таким образом, еще один выходец из русской крестьянской семьи занимает место на вершине чекистской иерархии, пройдя за два с небольшим года путь от старшего лейтенанта госбезопасности до комиссара госбезопасности 3-го ранга (14 марта 1940 года), что соответствовало званию генерал-лейтенанта.
Тем временем война стремительно приближалась. Примерно в то же самое время, в марте 1940 года, немецкая журналистка и агент советской военной разведки Ильза Штёбе (оперативный псевдоним «Альта») благодаря протекции сотрудника МИД Германии Рудольфа фон Шелиа (оперативный псевдоним «Ариец»), которого она же и завербовала, получила место в пресс-службе этого министерства. В конце декабря 1940 года «Альта» передала в Москву полученную от «Арийца» информацию о том, что 18 декабря 1940 года Гитлер подписал директиву № 21 «Вариант “Барбаросса”» (нем. «Fall Barbarossa»), согласно которой вооружённым силам Германии предписывалось «разгромить Советскую Россию в ходе одной кратковременной кампании».
Перед советскими органами была поставлена задача установить сроки возможного нападения на СССР. Как мне рассказал мой хороший товарищ, известный историк, ветеран внешней разведки Арсен Беникович Мартиросян, «о том, что нападение состоится в июне, гитлеровцы проговорились еще на исходе зимы и весной 1941 года. Из разных источников советская разведка получила сведения, что гитлеровское командование планирует напасть на СССР после окончания весенне-полевых сельхозработ с тем, чтобы успеть захватить советские посевы зерновых зелеными». А всего, по данным Арсена Бениковича, «сто тридцать три раза в донесениях всех видов разведки прозвучал июнь месяц, причем как приблизительно, ориентировочно, относительно точно, так и, наконец, абсолютно точно, то есть с указанием точной даты и часа начала агрессии».
Однако мы знаем, что Сталин не всегда и не во всем доверял сообщениям зарубежных резидентур – выше мы уже имели случай в этом убедиться. Но у него были и другие источники, которым он доверял больше, и среди них – контрразведка, которую возглавлял Федотов.
Контрразведчики хорошо знали, что немецкую разведку в Москве возглавляет Эрнст-Август Кёстринг – уроженец Серебряных Прудов под Москвой, сын управляющего имением графа Шереметева. Его земляком был будущий Маршал Советского Союза Василий Иванович Чуйков, отец которого был конюхом в том же имении. Именно на КП Чуйкова в Берлине утром 1 мая 1945 года бывший помощник Кёстринга в Москве, начальник Генерального штаба сухопутных войск Ганс Кребс вел переговоры с Чуйковым о капитуляции, а потом застрелился в бункере Гитлера.
Кёстринг, участник Первой мировой войны на стороне Германии, свободно владел русским языком и еще в 1931 году был назначен военным атташе посольства Германии в Москве. Оставаясь на этой должности с перерывами вплоть до начала войны, он проделал путь от полковника до генерала пехоты. В Москве его особняк находился в Хлебном переулке. Именно это обстоятельство и решил использовать Федотов с помощью своего суперагента Николая Кузнецова.
Простой сибирский парень, земляк Фитина, будущий Герой Советского Союза Николай Кузнецов (оперативный псевдоним «Колонист») был высоким, стройным, голубоглазым блондином, владел шестью диалектами немецкого языка и мог при необходимости говорить по-русски с немецким акцентом, прямо-таки завораживая собеседника. Именно Федотов в 1938 году взял его к себе, оформив под личную ответственность как особо засекреченного спецагента с окладом содержания по ставке кадрового оперуполномоченного центрального аппарата.