В это время Сталин уже принял окончательное решение о замене руководителя НКВД. Он подбирал кандидатуру, которая должна была отвечать «новым требованиям». Да и вообще, нужно же было кого-то сделать виноватым за середину 30-х.
Есть различные мнения по поводу того, кого Сталин хотел видеть в этом качестве. К примеру, существует версия, что этот пост предлагался В. П. Чкалову, прославленному летчику, популярному как в стране, так и за рубежом, имидж которого наверняка мог несколько сгладить неприглядную репутацию, заработанную НКВД в 30-е годы. Но, думается, Сталину скорее был нужен профессионал с опытом работы в ЧК, причем всесоюзно не запятнанный кровью репрессий 30-х годов, и Берия в данном случае был фигурой вполне подходящей: чекист, партийный работник высшего ранга, хозяйственник, достаточно образованный, квалифицированный и работоспособный.
17 ноября 1938 года выходит Постановление СНК СССР и ЦК ВКП(б) за подписью Молотова и Сталина «Об арестах в прокурорском надзоре и ведении следствия», в котором были отмечены крупные недостатки и извращения в работе органов НКВД. Наличие данного документа является самым красноречивым свидетельством того, что с Ежовым было уже покончено, а вот назначенный 29 сентября 1938 года начальником ГУГБ Берия, наоборот, вел активную деятельность и вникал в работу аппарата НКВД.
Как вспоминает П. А. Судоплатов: «В июле 1938 года судно, на котором я находился, пришвартовалось в Ленинградском порту. Я тут же выехал ночным поездом в Москву… На следующий день рано утром я был вызван к Берия, новому начальнику ГУГБ НКВД, первому заместителю Ежова. До этого о Берия я знал только то, что он возглавлял ГПУ Грузии в 20-х годах, а затем стал секретарем ЦК КПГ… Моя первая встреча с Лаврентием Павловичем продолжалась, кажется, около четырех часов. Он задавал мне вопрос за вопросом, желая знать обо всех деталях операции против Коновальца и об ОУН с начала ее деятельности… Берия проявил большой интерес к диверсионному партизанскому отряду, базировавшемуся в Барселоне, и т. д.».
Да, Берия настойчиво интересовался всеми сторонами текущей оперативной работы. Более того, первое, что он сделал, став заместителем Ежова, – переключил на себя связь с наиболее ценной агентурой, ранее находившейся в контакте с руководителями ведущих отделов и управлений НКВД. Это, возможно, было простым желанием продемонстрировать московскому аппарату, что приехал не провинциал, а деятельный профи. Вероятно, Берия, носивший пенсне, что делало его похожим на скромного служащего, специально выбрал для себя этот образ: в Москве его в то время никто не знал, и люди при встрече не фиксировали внимание на столь ординарной внешности. Это давало ему возможность посещать явочные квартиры в Москве для бесед с агентами, оставаясь неузнанным.
В ноябре 1938 года Ежов Н.И. направил письмо в ЦК ВКП(б) на имя Сталина, в котором, указывая на целый ряд своих ошибок и просчетов, допущенных в период работы в должности Наркома внутренних дел, попросил освободить его от занимаемой должности.
Разумеется, он прекрасно осознавал, что ему угрожает, и таким образом еще пытался смягчить неизбежную расправу.
24 ноября 1938 года последовало решение Политбюро ЦК ВКП(б), удовлетворившее его просьбу «ввиду изложенных в заявлении товарища Ежова Н. И. мотивов, а также принимая во внимание его болезненное состояние…»
Кстати, С. Л. Берия в своих воспоминаниях утверждает, что в этот период Ежов сильно пил и даже отравил свою жену, не дожидаясь ее ареста. В общем-то, это вполне укладывается в логику того времени, реалии тогдашней повседневности, законности и стереотипы мышления. Ведь и сам Н. И. Ежов только в июне 1937 года представил на утверждение в Политбюро расстрельный список из 3170 фамилий политических заключенных, а в июле 1937 года был награжден орденом Ленина «За выдающиеся успехи в деле руководства органами НКВД и выполнение сложных и ответственных правительственных заданий».
Сталин действовал последовательно: 25 ноября 1938 года Указом Президиума Верховного Совета СССР Н. И. Ежов был освобожден от должности наркома НКВД, но сохранил за собой должности секретаря ЦК ВКП(б), председателя Комиссии партийного контроля и Наркома Водного транспорта СССР. Этим же числом Л. П. Берия назначается на должность Народного комиссара внутренних дел.