22 августа 1938 г. Берия был назначен 1-м заместителем наркома внутренних дел. Днем раньше закончила работу 2-я сессия Верховного Совета СССР, и член Президиума Верховного Совета Берия еще в Москве. Сразу же после нового назначения он вечером 22 августа был принят Ежовым на Лубянке. Предстоящая работа в НКВД означала, что пост 1-го секретаря ЦК КП(б) Грузии Берия должен оставить. Передача дел и проведение пленума ЦК потребовали его присутствия в Тбилиси. Пленум ЦК КП(б) Грузии, освободивший Берию от работы, состоялся 31 августа. Вероятнее всего, последние дни пребывания в Грузии Берия провел с пользой. Он вполне мог выбрать преданных ему людей для руководящей работы в НКВД. И действительно, вскоре в столицу потянулись кадры грузинских чекистов, занимая ключевые посты на Лубянке. В начале сентября Берия возвратился в Москву и приступил к работе в НКВД, 4 сентября во второй половине дня он вновь в кабинете Ежова и пробыл там до вечера.

Назначение Берии морально подкосило Ежова. Он запил пуще прежнего. Вернувшийся с Дальнего Востока в Москву 25 августа Михаил Фриновский, еще формально числившийся 1-м заместителем наркома внутренних дел, застал в НКВД обстановку тревоги и паники: «Я Ежова вообще никогда в таком удрученном состоянии не видел. Он говорил: «Дело дрянь» — и сразу же перешел к вопросу о том, что Берия назначен в НКВД вопреки его желанию». Все дни с 22 августа по 4 сентября Ежов и его окружение лихорадочно завершали оформление дел на арестованных ранее чекистов. Они не должны были попасть в руки Берии. Никто не дал бы гарантии, что, будучи допрошены Берией, они не начнут давать показания теперь уже на Ежова. Их массовый расстрел был проведен 29 августа.

Ежов еще пытался как-то ограничить влияние Берии в НКВД, хотел выдвинуть бериевского недруга Станислава Реденса на должность своего 2-го зама, возродить коллегиальное руководство НКВД. Но было поздно. Берия быстро прибирал к рукам дела и ввел порядок, согласно которому вся документация НКВД, направляемая в ЦК и на периферию, была действительна лишь при наличии и его подписи в дополнение к подписи Ежова. По совместительству Берия возглавил важнейшее 1-е управление (госбезопасность) НКВД. Теперь он диктовал, кто и когда должен быть арестован. Одновременно он разработал новую структуру НКВД, которая без промедления была утверждена Сталиным. Новая структура — новые вакансии. И теперь полным ходом идет чистка аппарата НКВД, идут аресты в ежовском окружении.

Завершался Большой террор. 8 октября 1938 года Политбюро поручило специально сформированной комиссии в течение десяти дней подготовить проект документа от имени ЦК, СНК и НКВД о «новом порядке проведения арестов, о прокурорском надзоре и о ведении следствия». Комиссию возглавил Ежов, а в ее состав вошли Берия, завотделом руководящих партийных органов ЦК Георгий Маленков, прокурор Андрей Вышинский и нарком юстиции Н.М. Рычков.

Комиссия провела несколько встреч в кабинете Ежова. В результате было подготовлено постановление ЦК ВКП(б) и СНК СССР «Об арестах, прокурорском надзоре и ведении следствия», которое положило конец так называемым массовым операциям НКВД. 17 ноября 1938 года постановление было утверждено на Политбюро. Таким образом, Ежову, начавшему по приказу Сталина массовую бойню, пришлось самому разрабатывать меры по обузданию террора.

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

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

Между тем всего в ходе Большого террора были арестованы чуть больше 1,5 миллиона человек, из них осуждены 1 миллион 344 тысячи, в том числе расстреляны почти 700 тысяч человек. В ходе начавшегося при Берии пересмотра дел были освобождены, по разным оценкам, от 100 до 150 тысяч человек. В основном за счет тех, кого арестовали, но не успели осудить до 17 ноября 1938 г. — момента окончания Большого террора. Только в 1939 г. по прекращению дел были освобождены 83 тысячи человек.

Накануне и после назначения Берии наркомом по центральному аппарату НКВД прокатилась волна арестов. «Взяли» все окружение Ежова, всю верхушку. А руководителей региональных НКВД Берия арестовывал просто партиями. Об этом рассказал на допросе в 1953 году Меркулов. В Москву была вызвана группа руководителей региональных НКВД (от 15 до 20 человек), «все они по одному вызывались из приемной в кабинет наркома и здесь же арестовывались». Как пояснил Меркулов, «операция эта была проведена Берией».

Теперь в кабинетах Лубянки воцарились бериевцы. Когда первые из них в сентябре 1938 года появились на Лубянке, они одним своим видом внушали Ежову ужас. «Особенно бросался в глаза 130-килограммовый Богдан Кобулов». Своих жертв он «избивал кулаками… прыгал на них и наваливался своим огромным весом. Его любимым орудием пыток была дубинка». За широкие плечи Берия прозвал его Самовар.

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

Следственные методы 1937 г. прочно укоренились в системе госбезопасности. Прибывшее на смену ежовским кадрам новое чекистское поколение приняло их как эстафету. Как показывал на следствии Меркулов: «В Лефортовской тюрьме было жутко проходить, слыша крики избиваемых. Я не мог заснуть ночами, вспоминая эти картины. Избиение арестованных имело место и в кабинетах следователей в наркомате. Так продолжалось примерно до середины 1939 года, когда бить в помещении наркомата было запрещено, и били арестованных только в Лефортовской и Сухановской тюрьмах, на перевод куда требовалось отдельное разрешение Берии, мое или Кобулова, а, возможно, это также делалось с разрешения начальников следственных частей». Участвовал в избиениях и Берия. Как показал Меркулов: «В моем присутствии Берия несколько раз бил арестованных, в своем кабинете и в тюрьме — рукой и резиновой палкой».

Практически весь инструментарий, все методы, наработанные в годы Большого террора, остались на вооружении НКВД. Продолжал использоваться пресловутый закон от 1 декабря 1934 г. об ускоренном и упрощенном рассмотрении дел на Военной коллегии, продолжалась практика утверждения Сталиным и Политбюро «расстрельных списков». Внесудебный орган расправы Особое совещание при наркоме внутренних дел получило новые полномочия — выносить решения о конфискации имущества. Даже, когда надо, вновь создали чрезвычайную тройку — решением Политбюро от 5 марта 1940 г. для расправы над военнопленными польскими офицерами и гражданскими лицами, арестованными в западных областях. И именно Берия внес в Политбюро предложение всех их расстрелять как «закоренелых и непримиримых врагов», что и было сделано весной 1940 г. Было казнено 21 857 польских граждан. Это чудовищное преступление известно сегодня как «Катынское дело» (по названию местности, где впервые были найдены тела расстрелянных поляков). До сих пор российская власть скрывает обстоятельства этого преступления, засекретив постановление Главной военной прокуратуры о завершении расследования в 2004 г.

После провала попыток решить проблему уголовной преступности в Москве «законными» средствами Берия 21 февраля 1940 г. обратился с письмом к Молотову, в котором предлагал арестовать и решением Особого совещания НКВД заключить в исправительно-трудовые лагеря сроком до 8 лет «нелегально проживающих в Москве и ее области 5—7 тысяч человек уголовно-преступного элемента», а 300 человек «профессиональных бандитов и грабителей, имеющих неоднократные судимости и регистрации за грабежи и кражи», расстрелять, оформив их дела на Военной коллегии. В Политбюро одобрили его рвение. Резолюция Сталина гласила: «За. Расстреляйте человек 600. Ст.», и следовали подписи Молотова, Ворошилова и Кагановича.

И действительно, что там возиться с ведением следствия, доказательствами в суде — достаточно формальных признаков: ранее судился, прописки нет. В то время Берия, как и его вдохновитель Сталин, верили в эффективность чрезвычайных мер. Этот инструмент казался им безотказным.