Когда познакомились Берия и Сталин, достоверно неизвестно. Некоторые историки относят это событие ко времени подавления грузинского восстания 24-го года. Сын Лаврентия Павловича Серго о времени знакомства отца со Сталиным ничего не пишет, отмечает только тот очевидный факт, что «глава партии и государства санкционировал его назначение на пост руководителя Грузии и последующий перевод в Москву». Неясно, однако, знал ли Иосиф Виссарионович Берию к 1931 году лично или полагался на рекомендации своих соратников — Орджоникидзе и Микояна. Скорее последнее, ведь тот же Серго Лаврентьевич утверждает, что уже в бытность главой коммунистов Закавказья отец «еще при жизни Серго Орджоникидзе направил через него ряд писем Сталину, в которых не скрывал своей позиции: НКВД ведет планомерное уничтожение грузинской интеллигенции, грузинского народа». Раз письма вождю Лаврентию Павловичу приходилось передавать только при посредничестве члена Политбюро Орджоникидзе, то скорее всего непосредственного личного контакта, а тем более тесных, доверительных отношений между Берией и Сталиным еще не существовало. Они появились только с переездом Лаврентия Павловича в Москву. Примечательно, что этот переезд произошел уже после конфликта Сталина и Орджоникидзе и самоубийства последнего в феврале 37-го. Значит, здесь сыграл свою роль и другой покровитель Берии — Анастас Иванович Микоян, вместе с которым они работали в начале 20-х годов. Именно Микоян курировал НКВД в бытность главой органов Ежова и скорее всего предложил Сталину подходящую замену для чересчур активного и грозящего стать неуправляемым «стального наркома». Провинциал, не имевший прочных связей в центре и в аппарате НКВД, но с опытом чекистской работы, Берия оказался вполне подходящей кандидатурой.
В Закавказье Лаврентий Павлович принял активное участие в терроре 37–38 годов, широко применял санкционированное Ежовым и Сталиным избиение подследственных. На февральско-мартовском Пленуме 1937 года он сообщил, что только за последний год в Грузию вернулось почти полторы тысячи меньшевиков, дашнаков и мусаватистов, причем «за исключением отдельных единиц, большинство из возвращающихся остаются врагами Советской власти, являются лицами, которые организуют контрреволюционную, вредительскую, шпионскую, диверсионную работу. Мы знаем, что с ними нужно поступить, как с врагами».
Но вскоре на долю Берии выпала задача умерить размах репрессий. В августе 38-го Лаврентия Павловича назначили первым заместителем наркома внутренних дел СССР Н.И. Ежова, вместо М.П. Фриновского, поставленного во главе второстепенного Наркомата Военно-Морского Флота. И Михаилу Петровичу, и Николаю Ивановичу вскоре действительно предстояло «потонуть» (недаром Ежов незадолго до прихода Берии был назначен наркомом водного транспорта). Прежние руководители НКВД сделали отчаянную попытку свалить Лаврентия Павловича. В покаянном письме Сталину в конце ноября, уже после своего удаления из НКВД, Ежов признался: «Переживал назначение т. Берия. Видел в этом элемент недоверия к себе, однако думал, все пройдет. Искренне считал и считаю его крупным работником, я полагал, что он может занять пост наркома. Думал, что его назначение — подготовка моего освобождения (правильно думал! — Б. С.). Фриновский советовал: «Держать крепко вожжи в руках. Не хандрить, а взяться крепко за аппарат, чтобы он не двоил между т. Берия и мной. Не допускать людей т. Берия в аппарат». Фриновский в начале 30-х работал председателем ГПУ Азербайджана и часто конфликтовал с главой Закавказского ГПУ Берией. Теперь Михаил Петрович предупреждал Ежова, какой опасный это враг. Решено было представить Сталину компрометирующий материал на Берию — данные о его службе в мусаватистской контрразведке. Однако Сталин уже был в курсе, как обстояло дело в действительности (вспомним письмо Павлуновского), да и судьбу Ежова он давно предопределил. Поняв, что его песенка спета, Николай Иванович, по русскому обычаю, ушел в запой. 23 ноября 1938 года он подал прошение об отставке. 24 ноября Политбюро освободило Ежова от должности наркома внутренних дел, сохранив за ним уже ничего не значившие посты секретаря ЦК, председателя Комитета Партийного Контроля и наркома водного транспорта. В апреле 39-го Николая Ивановича арестовали, а в феврале 40-го арестовали. Преемником Ежова стал Берия.