Недавние «герои-чекисты» почуяли недоброе, и некоторые попытались предупредить свой арест. Широкий резонанс в ежовском наркомате получило известие о бегстве за границу одного из высоких чинов этого ведомства, начальника УНКВД Дальневосточного края Г.С. Люшкова. В 1937-м — начале 1938 г. под его руководством проводились аресты, расстрелы, депортации из приграничных районов в Среднюю Азию советских корейцев. В конце мая 1938 г. Политбюро приняло решение освободить Люшкова от работы на Дальнем Востоке и отозвать его в центральный аппарат НКВД. Опытный Люшков понял, что означает это «повышение». В ночь с 12 на 13 июня, прихватив ценные документы, под видом инспекционной поездки он перешёл границу с Маньчжоу-Го. В дальнейшем Люшков сотрудничал с японской разведкой, сообщая ценные данные. В августе 1945 г. отступавшие японцы застрелили много знавшего перебежчика.
Побег Люшкова был сильным ударом по Ежову, на которого в любом случае ложилась ответственность за столь крупные провалы. Видимо, именно тогда Ежов почувствовал всю шаткость своего положения. В конце ноября 1938 г., уже после своего смещения, Ежов в своеобразном письме-исповеди на имя Сталина отмечал: «Решающим был момент бегства Люшкова. Я буквально сходил с ума. Вызвал Фриновского и предложил вместе поехать докладывать Вам. Один был не в силах. Тогда же Фриновскому я сказал: Ну теперь нас крепко накажут… Я понимал, что у Вас должно создаться настороженное отношение к работе НКВД. Оно так и было. Я это чувствовал всё время».
Очень скоро Ежову пришлось ещё раз убедиться, что предчувствия его не обманули. В августе первым заместителем Ежова был назначен секретарь ЦК КП Грузии Л.П. Берия. Внешне Ежов оставался в фаворе и силе, но рядом с ним появился человек, которого сам нарком внутренних дел по доброй воле никогда бы не выбрал себе в заместители. «Переживал и назначение т. Берия, — признавался Ежов в уже цитированном письме на имя Сталина. — Видел в этом элемент недоверия к себе, однако, думал всё пройдёт. Искренне считал и считаю его крупным работником, я полагал, что он может занять пост наркома. Думал, что его назначение — подготовка моего освобождения».
Лёгкость, с которой смещали и арестовывали ближайших сотрудников Ежова и назначали на их место новых людей, свидетельствовала о бессилии наркома внутренних дел. В отчаянии он попытался предпринять некоторые контрмеры. Как признавался Ежов Сталину, на это его подталкивал также Фриновский, находившийся с Берия в плохих отношениях. Фриновский доказывал Ежову, что с Берия невозможно сработаться, что он будет предвзято информировать Сталина о положении в наркомате. Фриновский советовал: «Держать крепко вожжи в руках. Не хандрить, а взяться крепко за аппарат, чтобы он не двоил между т. Берия и мной. Не допускать людей т. Берия в аппарат». Одновременно активизировался сбор компрометирующих Берия материалов. По совету Фриновского Ежов передал их Сталину.
Очевидно, однако, что в сложившейся ситуации от Ежова уже ничего не зависело. Судорожно пытаясь остаться на плаву, он, несомненно, понимал, что кадровая чистка в НКВД рано или поздно дойдёт до наркома. Не справляясь с нервными перегрузками, Ежов, по некоторым свидетельствам, начал беспробудно пьянствовать.
С октября сталинские манёвры вокруг НКВД стали более активными. 8 октября Политбюро сформировало комиссию, которой поручалось в короткий срок подготовить проект постановления ЦК, СНК и НКВД о новой установке по вопросу об арестах, прокурорском надзоре и ведении следствия. Председателем комиссии был назначен пока Ежов, а в её состав вошли Берия, прокурор СССР Вышинский, председатель Верховного суда СССР Рычков и курировавший в ЦК ВКП(б) деятельность административных органов Маленков. Для подготовки документа комиссии отводился десятидневный срок, причём в первоначальном проекте постановления, написанном рукой Кагановича, срок работы комиссии не оговаривался и был внесён в окончательный вариант постановления Сталиным[513]. Несмотря на это, постановление СНК и ЦК ВКП(б) «Об арестах, прокурорском надзоре и ведении следствия» было утверждено Политбюро лишь 17 ноября, т.е. более чем через месяц после создания комиссии. Вряд ли столь значительное время понадобилось для составления проекта постановления. Судя по протоколам Политбюро, Сталину потребовался этот месяц для проведения дополнительной кадровой чистки в аппарате НКВД. С 8 октября по 17 ноября Политбюро санкционировало назначение нового начальника секретариата НКВД, направило на руководящие должности в отдел кадров НКВД группу инструкторов отдела руководящих партийных органов ЦК ВКП(б), назначило новых начальников иностранного отдела и оперативного отдела Главного управления государственной безопасности НКВД, а также нового начальника управления по Ленинградской области (многие новые работники были людьми Берия) и т.д.[514] Складывается впечатление, что перед решительным ударом Сталин, как обычно, старался предупредить любые неожиданности.