В ноябре 1936 г. путем объединения аппаратов Секретаря НКВД (этот пост занимал ближайший помощник бывшего наркома Ягоды старший майор ГБ Павел Петрович Буланов) и Оперативного секретаря наркома (им был известный северокавказский чекист Яков Абрамович Дейч, с 1931 г. работавший в Москве) был создан Секретариат НКВД СССР. Его начальником был назначен Дейч. Федотов служил под руководством Дейча в Грозном. 25 апреля 1937 г. Федотов был направлен в распоряжение Отдела кадров НКВД СССР, и уже 10 мая назначен помощником начальника Секретариата НКВД СССР — того же Дейча.

Дейч в Москве на этот раз не задержался. 16 августа 1937 г. он был назначен начальником управления НКВД по Азово-Черноморскому краю (в сентябре того же года край был разделен на Ростовскую область и Краснодарский край). Федотов, награжденный 11 июля орденом Красной Звезды, согласно приказу НКВД СССР от 28 августа 1937 г. также должен был отправиться на работу в Ростов. По данным историка М.А. Тумшиса, установившего факт перевода Федотова в Москву в апреле 1937 г. и его работы в Секретариате НКВД (ранее считалось, что Федотов попал в центральный аппарат только в ноябре 1937-го), вскоре «приказ был отменен. Федотов остался на работе в центральном аппарате НКВД. Это событие, вероятно, спасло ему жизнь. В марте 1938 г. Дейч был арестован и после продолжительных допросов «с пристрастием» умер в сентябре 1938 г. в одной из московских тюрем. Вполне возможно, что после ареста Дейча в тюремной камере мог оказаться и Федотов».

Любопытно, что Дейч (имевший прямое отношение к гибели Артузова и других чекистов) погиб еще в период «господства» в НКВД северокавказцев. Руководивший во второй половине 1937 — начале 1938 гг. контрразведкой в центральном аппарате НКВД СССР A.M. Минаев-Цикановский в своих показаниях на следствии уже после ареста в ноябре 1938 г. сообщил: «После ухода Дейча, заслонявшего собой обоих заместителей Ежова — Фриновского и Вельского, последние стали себя чувствовать увереннее». Также Дейч был одним из крайне немногочисленных руководителей местных управлений НКВД, не получившим в 1937 г. никаких наград (и к 20-летию ВЧК-НКВД в декабре, когда ордена получили почти все) и не избранным депутатом Верховного Совета СССР в том же декабре (из подчинявшихся непосредственно Центру можно назвать наркомов внутренних дел Карелии — вскоре арестованного Карла Тениссона, и Удмуртии — Дмитрия Шленова, а также назначенного в ноябре 1937 г. начальником УНКВД Курской области Алексея Боечина). Видимо, Дейч успел испортить отношения с бывшим сослуживцем Михаилом Фриновским (с апреля 1937 г. — 1-й заместитель Ежова и начальник Главного управления госбезопасности НКВД).

По данным историка В.Ю. Воронова, Федотов все-таки с августа 1937 г. работал в УНКВД по Азово-Черноморскому краю//Ростовской области, а в ноябре 1937 г. был переведен в центральный аппарат НКВД СССР. 10 ноября Федотов (за 5 дней до этого произведенный в капитаны ГБ) был назначен начальником 7-го (восточного) отделения 4-го отдела ГУГБ (с 28 марта 1938 г. — 1-го УГБ) НКВД СССР. С 1 августа1938 г. он уже стал помощником начальника 4-го отдела 1-го УГБ НКВД СССР, с 29 сентября 1938 г. — помощником начальника, а с 1 ноября 1938 г. заместителем начальника 2-го отдела ГУГБ НКВД. Одновременно с 8 октября по 22 декабря 1938 г. он был начальником следственной части 2-го отдела ГУГБ НКВД.

В период репрессий 1936–1938 гг. сотрудники СПО (с декабря 1936 г. — 4-го отдела ГУГБ) и их подразделений на местах играли важнейшую роль в арестах и следствии. СПО был центральным подразделением НКВД при подготовке «Московских процессов» 1936–1938 гг. (Зиновьева-Каменева, Пятакова-Радека, Бухарина-Рыкова). Для этого периода характерна частая сменяемость руководящего состава идеологической контрразведки, большая часть которого погибла. В 1936–1938 гг. сменилось 5 начальников СПО — 4-го отдела НКВД СССР. Были арестованы и расстреляны комиссар госбезопасности 1 ранга Я.С. Агранов (начальник 4-го отдела ГУГБ, зам. наркома НКВД), старший майор ГБ В.Е. Цесарский (начальник 4-го отдела ГУГБ в марте-мае 1938 г.), майор ГБ А.С. Журбенко (начальник 4-го отдела ГУГБ в мае-сентябре 1938 г.), заместители начальника отдела старший майор (затем комиссар ГБ 3 ранга) Б. Д. Берман, старший майор ГБ С.Г. Гендин, майор ГБ З.Н. Глебов-Юфа; застрелились комиссары ГБ 3 ранга В.М. Курский (начальник 4-го отдела ГУГБ в ноябре 1936 — апреле 1937 гг.), М.И. Литвин (начальник 4-го отдела ГУГБ в мае 1937 — январе 1938 гг.), зам. начальника отдела В.А. Каруцкий; погибло большинство других руководящих работников СО-СПО 20-х-30-х гг.

Работая все время в одном отделе, менявшем нумерацию, но все время занимавшимся борьбой с внутренней оппозицией, реальной и вымышленной, Федотов сумел не только не попасть под арест с неизбежным расстрелом, как почти все руководители СПО, но и удержаться в системе с последующим повышением.

Это удивительно еще и потому, что он участвовал в операциях, по завершении которых было нежелательно оставлять свидетелей. В качестве начальника восточного отделения 4-го отдела ГУГБ НКВД он ездил в сентябре 1937 г. в составе бригады ЦК ВКП(б) и Наркомвнудела СССР в Армению под руководством члена Политбюро, заместителя председателя СНК СССР А.И. Микояна, заведующего ОРПО ЦК ГМ. Маленкова и начальника 4-го отдела ГУГБ НКВД СССР старшего майора ГБ М.И. Литвина (в декабре 1937 г. избранного депутатом Верховного Совета от Армении).

Как через 20 лет сформулировали сотрудники Комитета партийного контроля при ЦК КПСС, Федотов и другие чекисты «активно участвовали в фальсифицировании обвинений на многих партийных и советских работников Армении, применяли к арестованным меры физического и морального воздействия». В результате погибли 1-й секретарь ЦК Армении Амаяк Аматуни, многие другие руководители республики, бывший председатель СНК Саак Тер-Габриэлян (в прошлом чекист, председатель ЧК Бакинской коммуны в 1918 г., заведующий Специальным (экономическим) отделом ВЧК в 1919 г.) во время допроса выбросился из окна (или был убит следователями); это происшествие вызвало подозрения Сталина.

В 1937–1938 гг. Федотов также вел следствие по делам бывшего полпреда СССР в Норвегии и Венгрии Александра Бекзадяна, бывшего первого секретаря ЦК КП(б) Киргизии Максима Аммосова и других крупных руководителей, расстрелянных и через 20 лет реабилитированных, что сыграло роль в последующей судьбе Петра Васильевича.

При новом наркоме Л.П. Берия (с сентября 1938 г.) сменяемость руководства 2-го отдела ГУГБ также была частой, но уже не сопровождалась репрессиями. Должность начальника отдела занимали старший майор ГБ (затем комиссар ГБ 3 ранга) Богдан Захарович Кобулов (сентябрь 1938 — июль 1939) и старший майор ГБ Иван Александрович Серов (июль-сентябрь 1939). После отъезда Серова на Украину 4 сентября 1939 г. отдел возглавил майор ГБ П.В. Федотов, в апреле этого года награжденный орденом Красного Знамени.

На декабрь 1939 г. структура 2-го (секретно-политического) отдела ГУГБ НКВД СССР включала в себя 12 отделений:

1-е — разработка троцкистов, зиновьевцев, правых оппозиционеров, мясниковцев, шляпниковцев, исключенных из ВКП(б), закордонная работа (начальник — капитан ГБ Яков Наумович Матусов;

2-е — разработка бывших меньшевиков, анархистов, эсеров, бундовцев, клерикалов, провокаторов, жандармов, контрразведчиков, карателей, белоказаков, монархистов;

3-е — борьба с украинской, белорусской, карело-финской националистической оппозицией;

4-е — агентурная разработка антисоветских партий дашнаков, тюркско-татарских националистов, грузинских меньшевиков, муссаватистов;

5-е — разработка литераторов, работников печати, издательств, театров, кино, деятелей культуры и искусства;

6-е — разработка и обслуживание Академии наук, научно-исследовательских институтов, научных обществ;

7-е — выявление и разработка антисоветских организаций учащейся молодежи, системы Наркомпроса, детей репрессированных;

8-е — обслуживание системы Наркомздрава и его учебных заведений;