Летом 1938 года он назначается первым заместителем наркома внутренних дел СССР, сменив, тем самым, не только место жительства, но и масштаб деятельности. В решении о замене Ежова Берией принимали определенное участие Молотов и Ворошилов, деятели, находившиеся в тот период времени с вождем в наиболее близких отношения. А после помпезного празднования 15-летия Грузинской ССР в 1936 году близко соприкоснувшиеся с ее главой.
7 ноября 1938 года Политбюро ЦК ВКП(б) утвердило совместное Постановление Совнаркома и ЦК ВКП(б) «Об арестах, прокурорском надзоре и ведении следствия». Этим документом категорически осуждались порочная система ежовских «принципов» организации работы НКВД, приведших к огромному числу необоснованных арестов и казней.
Спустя полмесяца трио в составе Сталина, Молотова и Ворошилова обрабатывало Ежова несколько часов кряду, дабы без особой шумихи добиться его согласия покинуть пост главы НКВД.
Берия умел производить самое благоприятное впечатление и, будучи земляком Сталина, тем не менее, не кичился данным преимуществом. К числу его недостатков нельзя отнести чрезмерную надоедливость. Берия очень отличился перед самим вождем весьма предупредительным отношением к его матери. Он окружил родительницу Сталина неусыпным и в то же время ненавязчивым вниманием. Очевидно, Берия периодически информировал вождя о состоянии Екатерины Джугашвили, здоровье которой постепенно ухудшалось.
Осенью 36 года Сталин неожиданно приезжал навестить мать. Их рандеву было непродолжительным. Берия отлично был осведомлен о занятости своего шефа и дал ему шанс не только увидеться с матерью, но заодно и фактически попрощаться с ней еще при жизни.
Мать Сталина умерла 4 июня 37 года, когда в Москве полным ходом раскручивался «заговор» красных военачальников. Естественно, Сталин не мог покинуть столицу в такой критический момент. Берия самостоятельно и превосходно организовал похороны со всеми необходимыми почестями. При этом он не допустил ни малейшей тени бестактности в этом весьма деликатном вопросе.
В системе НКВД Берия первоначально контролирует восстановленное Главное управление государственной безопасности (ГУГБ) и постепенно начинает перевод своих людей на ключевые посты. Взяв полностью бразды правления в свои руки, он начинает с того, с чем не справился Ежов: чистки органов НКВД.
Только за 1939 год ротация оперативных кадров энкавэдешни-ков составила 62%, из 6174 руководителей было сменено 3830 человек. Одновременно Берия лично разбирается с наиболее громкими фигурантами ежовских судилищ. Он отчетливо представляет, что мертвых не воскресить и, в то же время, понимает политическую пагубность для государства публичного признания факта гибели мало повинных сограждан. Беседуя с вдовой Бухарина совместно со своим сотрудником, одним из братьев Кобуловых, Берия зондировал ее позицию именно относительно данного аспекта.
В большой тени, отброшенной персонами Ежова и Берии, несколько затерялись другие достаточно важные фигуры конгломерата систем карательно-репрессивных органов.
20 июня 1933 года была учреждена Прокуратура СССР с целью дальнейшего «укрепления социалистической законности» на всей территории страны. Прокуратура Верховного Суда упразднялась, но в союзных республиках продолжали функционировать прокуратуры в составе наркоматов юстиции. На высшем уровне прокурорский надзор был отделен от судейства и наркомата юстиции, а ниже параллелизм продолжал действовать еще три с лишним года.
Лишь 20 июля 36 года совместным постановлением ЦИК и СНК был образован наркомат юстиции СССР и из системы НКЮ союзных и автономных республик были выделены органы прокуратуры и следствия. Их передали в непосредственное подчинение Прокурора СССР. Процесс централизации советской прокуратуры был завершен.
Первым главным прокурором Советского Союза был И.А. Акулов, занимавший некоторое время должность первого заместителя начальника О ГПУ и слывший конкурентом Ягоды. Прокурорство Акулова длилось не слишком долго, он занял затем кресло секретаря Президиума ЦИК и на этом его карьера закончилась, столь же бесславно как у Крыленко…
Бывший меньшевик Вышинский А.Я. сменил Акулова на посту главы Прокуратуры СССР, которая мыслилась как организация, долженствовавшая стать действенным заслоном по пути превышения инстанциями НКВД своих полномочий. Функции которого расширились с учреждением 5 ноября 1934 года Особого совещания при наркомвнуделе СССР. По некоторым данным, проект совместного постановления ЦИК и СНК об особом совещании был подготовлен под опекой Кагановича и заимствован с царского законодательства.