Однако долго оставаться беспартийным Федотов не мог. В июле 1937 года старший лейтенант ОГПУ (что соответствовало званию майора в РККА) Павел Федотов, удостоенный к тому времени высшей чекистской награды – нагрудного знака «Почетный работник ВЧК – ГПУ», был вновь принят в ряды ВКП(б). Являясь одним из ведущих специалистов по Северному Кавказу, в сентябре того же года он был откомандирован в распоряжение отдела кадров НКВД СССР. 10 ноября его назначают начальником 7‑го (восточного) отделения 4‑го отдела ГУГБ НКВД. Начинается самый сложный период в его работе в органах госбезопасности. На это время приходится наиболее активный период чисток, осуществляемых Ежовым по прямому указанию Сталина.
Однако Петр Васильевич преодолел этот период вполне благополучно. Здесь сказались, видимо, два факта. Во-первых, до 1937 года он был беспартийным и хотя бы по этой причине не был замешан во внутрипартийных разборках, не примыкал к антисталинской оппозиции и все свои усилия сосредоточивал на добросовестном выполнении служебных обязанностей и информационно-аналитической работе. В характеристиках на Федотова отмечался недостаток у него инициативы. Это следует понимать так, что он не проявлял никакого рвения в фабрикации «липовых дел», зачастую раздувавшихся до вселенских масштабов. Исход таких «липовых дел» далеко не всегда мог быть благоприятным. Будучи отличным аналитиком, Павел Васильевич умел заглядывать далеко вперед.
Во-вторых, хотя в Москву Федотов был переведен с санкции Николая Ежова, с ним до работы в Москве он никак не был связан. На него нельзя было повесить ярлык «подручного палача», погубившего лучшие партийные кадры. Кроме того, вскоре в Москву был переведен и первый секретарь ЦК компартии Грузии Лаврентий Берия, назначенный сначала первым заместителем, а затем наркомом внутренних дел. Петра Федотова он знал по совместной работе на Кавказе. Уже в июле 1938 года Федотов с подачи Берии назначается заместителем начальника, а с сентября 1939 года – начальником 4‑го (секретно-политического) отдела ГУГБ НКВД.
В сентябре 1940 года следует очередное повышение Федотова. Он, получивший ранг комиссара госбезопасности 3‑го ранга, что соответствовало армейскому званию генерал-лейтенанта, назначается на должность начальника 3‑го (контрразведывательного) отдела ГУГБ НКВД, который спустя полгода был преобразован во 2‑е управление Наркомата госбезопасности. Это назначение на столь высокую должность было связано с активизацией работы германских и других спецслужб стран «Антикоминтерновского пакта» на территории СССР. Нашу страну наводнили «туристы», «журналисты», «инженеры» и прочие незваные визитеры, главной задачей которых являлось выяснение степени готовности СССР к большой войне. Москву под видом инженера в составе одной из делегаций нацистской Германии посетил даже начальник VI отдела РСХА (разведки гестапо) Вальтер Шелленберг.
Перед возглавляемыми Федотовым контрразведчиками в предвоенный период в качестве основной ставилась задача воспрепятствовать разведывательной деятельности спецслужб Третьего рейха на территории СССР, а также выяснять истинные планы Берлина в отношении нашей страны. С этой целью советские чекисты задействовали многочисленную агентуру, в том числе и весьма ценного помощника контрразведки довоенного периода Николая Кузнецова, который в годы войны стал Героем Советского Союза. Известно, что он под видом летчика-испытателя московского авиазавода, этнического немца по фамилии Шмидт, был подставлен сотрудникам ряда иностранных посольств, в том числе Германии и Японии. Действиями Кузнецова в тот период непосредственно руководил Федотов. В результате его работы чекисты получали важную информацию об истинных планах и намерениях Германии в отношении нашей страны.
Но это был не единственный источник информации чекистов по немецкой колонии в Москве. В двадцатых числах апреля 1941 года Федотов направил за своей подписью на имя заместителя наркома госбезопасности Всеволода Меркулова спецсообщение о содержании бесед военного атташе Германии в Москве генерал-майора Эрнста Кестринга и его сотрудников с коллегами немцев из военных миссий Финляндии, Италии, Японии, Венгрии и других стран «Антикоминтерновского пакта». Содержание этих материалов не вызывало сомнений: в ближайшее время Германия намерена напасть на СССР и только ищет предлога для оправдания своей агрессии.
Следует отметить, что замысел чекистской операции по оперативно-техническому проникновению в посольство нацистской Германии, располагавшееся в Хлебном переулке, также принадлежал Петру Федотову. По его указанию чекисты под предлогом устранения аварии водопровода в доме напротив проникли по подземным коммуникациям в здание германского посольства и установили спецтехнику в кабинете военного атташе. Аппаратура подслушивания день за днем фиксировала его переговоры с посетителями. Нацистского разведчика интересовали в первую очередь уровень боеготовности Красной Армии, состояние оборонной промышленности СССР, мобилизационная готовность нашей страны.