Весной 1938 года Сталин окончательно решил сместить Ежова с поста наркома внутренних дел. Великую чистку пора было постепенно сворачивать, а ее главного исполнителя — отправлять сначала в политическое, а затем и в физическое небытие. Уже 8 апреля 1938 года Ежова по совместительству назначили наркомом водного транспорта. Николаю Ивановичу пришлось забрать в новый наркомат многих преданных ему людей в центральном аппарате НКВД, что объективно ослабило его позиции в карательном ведомстве. Одновременно это помогло Сталину совершенно естественным образом поставить вопрос о необходимости укрепления руководства НКВД новыми кадрами. А самым подходящим кандидатом на пост первого заместителя Ежова Сталин счел Берию. Во-первых, человек ему безусловно преданный. Во-вторых, в отличие от Николая Ивановича, Лаврентию Павловичу чекистского опыта было не занимать: долгие годы возглавлял ГПУ Грузии, был и во главе закавказских чекистов. И этот опыт, в частности, в свете надвигавшейся войны мог пригодиться для операций за рубежом. Но главными, конечно же, при назначении Берии были соображения внутреннего порядка. Ежова и его людей требовалось как можно скорее убрать и из НКВД, и из жизни. А уж Лаврентий Павлович, с его-то опытом, легко разберется, кого из чекистов казнить, а кого миловать, да и по старой памяти быстро сможет заменить выбывших из строя ежовских выдвиженцев хорошо знакомыми ему кадрами закавказских чекистов.
И, как по заказу, для смещения Ежова представился замечательный повод. В июне 1938 года сбежал к японцам начальник Дальневосточного управления внутренних дел Г.С. Люшков, не без оснований опасавшийся ареста. Ежов понял, что скоро настанет его черед. В письме-исповеди Сталину в конце ноября, уже после своего удаления из НКВД, Николай Иванович писал: "Решающим был момент бегства Люшкова. Я буквально сходил с ума. Вызвал Фриновского и предложил вместе поехать докладывать Вам. Один был не в силах. Тогда же Фриновскому я сказал: "Ну, теперь нас крепко накажут…" Я понимал, что у Вас должно создаться настороженное отношение к работе НКВД. Оно так и было. Я это чувствовал все время".
Случай с Люшковым послужил предлогом для назначения 22 августа Берии первым заместителем наркома внутренних дел. Прежние руководители НКВД сделали отчаянную попытку свалить Лаврентия Павловича. В покаянном письме Сталину Ежов признался: "Переживал… назначение т. Берия. Видел в этом элемент недоверия к себе, однако думал все пройдет. Искренне считал и считаю его крупным работником, я полагал, что он может занять пост наркома. Думал, что его назначение — подготовка моего освобождения (правильно думал! — Б. С.)… Фриновский советовал: "Держать крепко вожжи в руках. Не хандрить, а взяться крепко за аппарат, чтобы он не двоил между т. Берия и мной. Не допускать людей т. Берия в аппарат". Фриновский в начале 30-х работал председателем ГПУ Азербайджана и часто конфликтовал с Берией как с одним из руководителей Закавказского ГПУ. Теперь Михаил Петрович предупреждал Ежова, какой опасный это враг. Решено было представить Сталину компрометирующий материал на Берию — данные о его службе в мусаватистской контрразведке. Однако Сталин уже был в курсе, как обстояло дело в действительности (вспомним письмо Павлуновского), да и судьбу Ежова он давно предопределил.
На долю Берии выпала задача умерить размах репрессий. 8 сентября 1939 года другой первый заместитель наркома внутренних дел М.П. Фриновский был назначен наркомом Военно-Морского Флота, а 29 сентября в ведение Берии перешло Главное управление Государственной Безопасности. К началу октября Ежов практически утратил контроль над основными структурами наркомата внутренних дел.