Старую чекистскую гвардию пора было убирать со сцены, и первой крупной жертвой внутренней чистки становится заместитель начальника саратовского краевого управления НКВД, комиссар государственной безопасности 3-го ранга И. И. Сосновский. В прошлом — резидент польской разведки в России, Сосновский был арестован в 1920 г. и тогда же перевербован, согласившись на сотрудничество при условии возвращения на родину после окончания следствия всех названных им агентов-поляков, что и было сделано. В дальнейшем Сосновский работал в подразделениях Особого и Контрразведывательного отделов ВЧК-ОГПУ в центре и на местах и к 1934 г. дорос уже до уровня заместителя начальника Особого отдела ГУГБ НКВД. В декабре 1934 года в составе бригады московских чекистов он выезжал в Ленинград, где принимал участие в расследовании обстоятельств убийства С. М. Кирова. Вероятно, именно в те дни Сосновский в очередной раз попался на глаза находившемуся там же Сталину, который выразил недовольство тем, что на такой ответственной работе находится бывший польский разведчик. После этого Сосновский в начале января 1935 года был переведен в Саратовский край на должность заместителя начальника местного УНКВД, где с тех пор и находился.

В 1936 году некоторые из проживающих в Москве польских коммунистов, обеспокоенные арестами в их среде, обратились в НКВД с заявлением, в котором высказали предположение, что именно Сосновский направляет органы госбезопасности по ложному следу. Кроме того, в ходе допросов арестованных поляков были получены «сведения» о шпионской работе Сосновского, так что в ноябре 1936-го он был арестован. Тогда же за решеткой оказались и многие другие чекисты польского происхождения — внутри НКВД вовсю шла охота на мифических польских агентов.

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

Однако основная чистка началась в НКВД в конце марта 1937 года после ареста бывшего наркома внутренних дел СССР Г. Г. Ягоды и продолжалась в наиболее интенсивной своей фазе примерно до конца октября того же года. За этот период были арестованы шесть из восьми начальников отделов Главного управления госбезопасности и треть руководителей основных региональных подразделений НКВД, занимавших эти должности на момент прихода Ежова.

К концу апреля 1937 года от Ягоды и арестованных к тому времени его бывших подчиненных удалось с помощью уговоров и избиений получить показания о якобы действующей в НКВД заговорщицкой организации, ставящей целью свержение существующего руководства и захват власти в стране.

С этого времени следствие ведется в режиме особой секретности, чтобы упоминаемые в показаниях имена «заговорщиков» не стали широко известны до того, как руководство НКВД определит, какие из них названы «правильно», а какие нет.

Заявления арестованных записывались сначала начерно, потом их корректировал начальник того отдела ГУГБ, который контролировал данное следствие, вслед за этим очень часто к делу подключался начальник Секретариата НКВД Я. А. Дейч, после чего отредактированный текст поступал на согласование к Фриновскому или Ежову, и уже с учетом их замечаний оформлялся окончательный вариант протокола допроса.

Если же показания, обличающие «заговорщиков», поступали из региональных управлений и исправить их было уже невозможно, приходилось вызывать арестованных в Москву и путем передопросов вынуждать их отказываться от обвинений в адрес тех чекистов, которым Ежов доверял и с которыми собирался работать и дальше.

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

Единственный из чекистов, награжденный четырьмя орденами Красного Знамени, Евдокимов в конце Гражданской войны работал заместителем начальника Особого отдела Юго-Западного фронта. Сталин в этот период был членом Реввоенсовета того же фронта, и результатом этого знакомства стали достаточно доверительные отношения, сложившиеся у Евдокимова с вождем.

В 1923 году Евдокимов возглавил Полномочное представительство ОГПУ по Северо-Кавказскому краю, и именно он в 1927 году из ряда аварий на угледобывающих предприятиях края создал в соответствии с поручением Сталина так называемое «Шахтинское дело», закончившееся первым в стране фальсифицированным процессом над врагами народа — вредителями. (Четвертый орден Красного Знамени был получен как раз за это.)

В период работы в Особом отделе Юго-Западного фронта, затем во Всеукраинской чрезвычайной комиссии и, наконец, в Северо-Кавказском крае Евдокимов подобрал и сплотил вокруг себя большую команду преданных ему чекистов, которых он продвигал по служебной лестнице, представлял к награждениям, брал, в случае необходимости, под защиту и т. д. Хотя некоторым и не нравилось его нежелание считаться с чьим-либо мнением, кроме своего, но во внеслужебной обстановке он держался подчеркнуто демократично, и это создавало ему дополнительный авторитет.

Сплачивало евдокимовцев не только общее дело, но и поощряемые шефом коллективные формы досуга. Один из северокавказцев, И. Я. Ильин, вспоминал позднее:

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

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