После ареста Ежова в его сейфе нашли досье, составленное на Сталина и лиц из его ближайшего окружения. А не так давно в Кремле, во время ремонтных работ обнаружилось, что ведомство Ежова регулярно «слушало» кабинет вождя.
НКВД стало предпринимать сепаратные акции, направленные против лиц, лояльных по отношению к Сталину и пользующихся его полным доверием. Особенно показательна история с Шолоховым. Органы подбирались к нему еще в 1936 году, когда в Вешенской, родной станице писателя, была вскрыта липовая «контрреволюционная организация». Однако тронуть его боялись. Сталин высоко ценил и любил Шолохова. Писатель не боялся открыто информировать вождя о тех безобразиях, которые творились на местах. Он решительно выступил против злоупотреблений в ходе коллективизации. В 1933 году писатель направил Сталину три письма, в которых описал тяжелое положение родного края.
Ознакомившись с письмами Шолохова, Сталин распорядился выслать в Вешенский район 120 тысяч пудов ржи, а в Верхне-Донской район 40 тысяч пудов. Таким образом, Шолохов своей отважной акцией, грозившей опалой, спас многие человеческие жизни.
Местное руководство явно было не в восторге оттого, что у них в регионе находится такой важный «канал» непосредственной связи со Сталиным. Отсюда и попытки скомпрометировать писателя. Они продолжились и в 1937 году, а в 1938-м стали уже совсем настойчивыми. Ростовское управление НКВД действовало еще более решительно, чем прежние партократы, прищученные Сталиным. Чекисты уже подготовили арест писателя. Однако некто Погорелов, заместитель начальника УНКВД Когана, предупредил писателя о готовящейся акции. Шолохов и Погорелов тайно выбрались в столицу, где и добились встречи со Сталиным, на которой тот решительно взял великого писателя под свою защиту.
Эта воистину детективная история свидетельствует о том, что органы НКВД становились все более и более неуправляемыми. Нужно было срочно менять их руководство.
Сталин не торопился и провел эту замену в два этапа. Сначала он сосватал Ежову своего давнишнего сторонника Берию. Он сделал Лаврентия Павловича заместителем наркома внутренних дел. Ежов же получил, в прибавку ко всем постам, новое назначение — наркомом водного транспорта. Это произошло в августе 1938 года. И уже очень скоро Ежов, занимавшийся делами «водного» наркомата, оказался оттертым от реального управления НКВД. Теперь все официальные документы, спускаемые «с верху», поступали уже на имя Берии. Наконец, 9 ноября Ежов был снят с поста наркома НКВД. Он еще протянет до 10 апреля 1939 года, когда произойдет его арест. Однако судьба Ежова была уже решена. Отныне он не имел политического влияния и стремительно деградировал в личном плане, ожидая ареста.
Надо сказать, что далеко не все чекисты были рады появлению нового начальства. Перед Берией была поставлена задача — прекратить массовый террор, а эти лихачи жаждали «продолжения банкета». В феврале 1939 года группа высокопоставленных чекистов, во главе с М.С. Кедровым, направила на имя Сталина письмо, в котором резко осуждался новый стиль руководства. Он был назван «фельдфебельским». Наверное, Сталин не мог читать этого письма без смеха. Получалось, что прежде, во времена Ежова и Ягоды, НКВД был прямо-таки демократическим учреждением, а теперь, когда он выпускал на волю десятки тысяч невинно осужденных, появился откуда-то неожиданно «фельдфебельский» стиль.