В январе 1925 года Петр Федотов назначается на должность помощника начальника контрразведывательного отдела Чеченского ГПУ. Принимает участие в разоружении Чечни и Дагестана. Как аналитик, хорошо знающий агентурно-оперативную обстановку на Северном Кавказе, он провел основательную подготовительную работу, что позволило руководству РККА верно ориентироваться в обстановке в этих районах. В ходе операции по разоружению Чечни и Дагестана Федотов руководил информационной и агентурной службами. Благодаря созданным им агентурным позициям среди местного населения чекистам удалось без привлечения регулярных войск РККА ликвидировать незаконные вооруженные формирования шейхов Ильясова и Ахаева, а впоследствии и шейха Аксалтинского.

В феврале 1927 года Федотова переводят в Ростов-на-Дону в Полномочное представительство ОГПУ по Северо-Кавказскому краю в качестве оперуполномоченного. Здесь, как и ранее в Грозном, он занимался борьбой с политическим бандитизмом. Регулярно выезжал в служебные командировки в Чечню и Дагестан, где чекисты добивали остатки вооруженных националистических банд. Руководство Полпредства по-прежнему высоко оценивало его работу. В служебных характеристиках за тот период отмечалось: «Весьма добросовестный, честный и преданный работник. Свою работу знает хорошо, проявляет в ней большую инициативу. В выполнении заданий медлителен, что окупается чрезмерной тщательностью работы и продуманностью подхода к ней».

В октябре 1930 года Федотов назначается начальником 6-го отделения Информационного отдела Полномочного представительства ОГПУ по Северо-Кавказскому краю. Уже через год, в ноябре 1931 года, он становится начальником отделения

Секретно-политического отдела, в задачу которого входила разработка внутренней оппозиции, а также проведение обысков, арестов и задержания «контрреволюционных элементов». Время было непростое. Бывший руководитель Полномочного представительства ОГПУ на Северном Кавказе Евдокимов инспирировал громкий судебный процесс над так называемой Промпартией. В ходе сфальсифицированного судебного процесса участников несуществующей партии обвинили в организации актов саботажа и диверсий на шахтах и промышленных предприятиях Донбасса, Ростовской и других областей, в связях с бывшими владельцами этих предприятий. На скамье подсудимых оказались представители старой технической и творческой интеллигенции, бывшие царские генералы и офицеры, военспецы РККА.

После убийства С.М. Кирова Сталин взял курс на политическую, а затем физическую ликвидацию лидеров внутрипартийной оппозиции. От чекистов требовалось решительно выкорчевывать контрреволюционные элементы. Эта кампания, начатая по инициативе Сталина, вылилась в трагические события 1937–1938 годов, получивших название «єжовщина». В результате массовых необоснованных репрессий против явных и вымышленных противников Сталина экономика страны к 1938 году пришла в упадок. Были парализованы целые ее отрасли, в том числе оборонная, поскольку видные «капитаны индустрии» были по ложным обвинениям арестованы, а многие из них расстреляны. Такое же положение было и в Красной Армии, боеспособность которой, как показали итоги Финской кампании 1939–1940 годов, резко упала по сравнению с 1935 годом.

В этот непростой период Петр Васильевич продолжал работать в секретно-политическом отделе Полпредства ОГПУ по Северному Кавказу. Довелось ему участвовать в кампании по раскулачиванию, в разработке местных троцкистских и эсеровских групп, местной творческой и технической интеллигенции. Таковым было время, и не следует его строго судить за это, тем более что фактов, свидетельствующих о его прямом участии в кровавых злодеяниях, нет. Работая в секретно-политическом отделе, Федотов основные усилия сосредоточивал на оперативно-аналитической работе. Участвуя в работе СПО, он даже не был членом ВКП(б).

Мы уже упоминали, что в 1919 году Федотов был принят в партию большевиков, однако в 1922 году автоматически выбыл из нее. Это объяснялось тем, что чекист с головой окунулся в оперативную работу, дни и ночи разрабатывая главарей националистического подполья в Чечне. Времени для регулярного посещения партийных собраний у него просто не было. Члены партийной ячейки проголосовали за его «автоматическое выбытие» из членов РКП(б). Симптоматично, что таким же образом из партии была исключена и жена Сталина — Светлана Аллилуева. Потребовалось личное вмешательство В.И. Ленина, чтобы восстановить ее в рядах РКП(б).

Однако долго оставаться беспартийным Федотов не мог. В июле 1937 года старший лейтенант ОГПУ (что соответствовало званию майора в РККА) Павел Федотов, удостоенный к тому времени высшей чекистской награды — нагрудного знака «Почетный работник ВЧК — ГПУ», был вновь принят в ряды ВКП(б). Являясь одним из ведущих специалистов по Северному Кавказу, в сентябре того же года он был откомандирован в распоряжение отдела кадров НКВД СССР. 10 ноября его назначают начальником 7-го (восточного) отделения 4-го отдела ГУГБ НКВД. Начинается самый сложный период в его работе в органах госбезопасности. На это время приходится наиболее активный период чисток, осуществляемых Ежовым по прямому указанию Сталина.

Однако Петр Васильевич преодолел этот период вполне благополучно. Здесь сказались, видимо, два факта. Во-первых, до 1937 года он был беспартийным и хотя бы по этой причине не был замешан во внутрипартийных разборках, не примыкал к антисталинской оппозиции и все свои усилия сосредоточивал на добросовестном выполнении служебных обязанностей и информационно-аналитической работе. В характеристиках на Федотова отмечался недостаток у него инициативы. Это следует понимать так, что он не проявлял никакого рвения в фабрикации «липовых дел», зачастую раздувавшихся до вселенских масштабов. Исход таких «липовых дел» далеко не всегда мог быть благоприятным. Будучи отличным аналитиком, Павел Васильевич умел заглядывать далеко вперед.

Во-вторых, хотя в Москву Федотов был переведен с санкции Николая Ежова, с ним до работы в Москве он никак не был связан. На него нельзя было повесить ярлык «подручного палача», погубившего лучшие партийные кадры. Кроме того, вскоре в Москву был переведен и первый секретарь ЦК компартии Грузии Лаврентий Берия, назначенный сначала первым заместителем, а затем наркомом внутренних дел. Петра Федотова он знал по совместной работе на Кавказе. Уже в июле 1938 года Федотов с подачи Берии назначается заместителем начальника, а с сентября 1939 года — начальником 4-го (секретно-политического) отдела ГУГБ НКВД.

В сентябре 1940 года следует очередное повышение Федотова. Он, получивший ранг комиссара госбезопасности 3-го ранга, что соответствовало армейскому званию генерал-лейтенанта, назначается на должность начальника 3-го (контрразведывательного) отдела ГУГБ НКВД, который спустя полгода был преобразован во 2-е управление Наркомата госбезопасности. Это назначение на столь высокую должность было связано с активизацией работы германских и других спецслужб стран «Антикоминтерновского пакта» на территории СССР. Нашу страну наводнили «туристы», «журналисты», «инженеры» и прочие незваные визитеры, главной задачей которых являлось выяснение степени готовности СССР к большой войне. Москву под видом инженера в составе одной из делегаций нацистской Германии посетил даже начальник VI отдела РСХА (разведки гестапо) Вальтер Шелленберг.