Вслед за Ягодой были арестованы, а затем и расстреляны начальники ведущих отделов: Иностранного — Артур Христианович Артузов; Спецотдела (шифровальная служба) — Глеб Иванович Бокий; Транспортного (борьба с диверсиями на транспорте) — Владимир Александрович Кишкин (до ареста замнаркома путей сообщения) и Александр Михайлович Шанин; Экономического (борьба с диверсиями и вредительством в промышленности) — Лев Григорьевич Миронов; Секретно-политического (борьба с враждебными политическими партиями) — Георгий Андреевич Молчанов; Оперативного (охрана политбюро, наружное наблюдение, аресты и обыски) — Карл Викторович Паукер.
Паукер, охранявший генерального секретаря, разонравился Сталину. Карл Викторович попал в органы госбезопасности самым странным образом. Он родился во Львове, который до Первой мировой войны входил в состав Австро-Венгрии. Никогда не учился, работал в парикмахерской отца, затем на кондитерской фабрике.
В Первую мировую войну его мобилизовали в австро-венгерскую армию. В апреле 1915 года фельдфебель Паукер попал в русский плен. Приветствовал революцию, из военнопленного превратился в активного борца за советскую власть. Его взяли в Иностранный отдел ВЧК, но быстро перевели в Оперативный отдел, которому поручили охрану руководителей партии и государства.
Карл Викторович, весельчак и балагур, веселил вождя. Сталин сделал его комиссаром госбезопасности 2-го ранга (это приравнивалось к армейскому званию генерал-полковник), наградил несколькими орденами. Но барская любовь рано или поздно заканчивается.
А Николай Иванович Ежов уже развернулся на новом поприще. Его имя гремело по всей стране. Его славили газеты. О нем слагали стихи:
Кто барсов отважней и зорче орлов?
Любимец страны, зоркоглазый Ежов.
Учился будущий нарком совсем мало: один класс начального училища (потом еще курсы марксизма-ленинизма при ЦК партии) и остался необразованным, малограмотным человеком, зато обладал каллиграфическим почерком.
Он начинал учеником в слесарно-механической мастерской, учился портняжному делу, трудился на кроватной фабрике. Несколько лет прослужил в армии — в запасном полку, потом в артиллерийских мастерских. После Гражданской войны работал в Казани в обкоме партии. Женился на Антонине Алексеевне Титовой, которая не только окончила гимназию, но и поступила в Казанский университет. Она отправилась в Москву и нашла себе место заведующей культотделом профсоюза химиков.
Вслед за ней в столицу переехал и Николай Иванович. В ЦК обратили внимание на молодого партийца: через полгода, в феврале 1922-го, Оргбюро ЦК командировало его секретарем обкома в Марийскую автономную область. На решении подпись секретаря ЦК Вячеслава Михайловича Молотова.
Историки тщетно пытаются понять, кто ворожил Ежову, кто включил его в партийную элиту, кто давал ему высокие должности. Связи и знакомства, конечно, большое дело в карьере. Но в те времена ощущался очевидный голод на партийные кадры, не хватало элементарно грамотных людей. А Николай Иванович был толковым работником с организаторской жилкой.
Он трудился в Краснококшайске (ныне Йошкар-Ола), в Семипалатинске, Оренбурге, в Кзыл-Орде (тогда столица Казахской АССР). Писатель Юрий Осипович Домбровский, отбывавший ссылку в Казахстане, писал, что среди его знакомых «не было ни одного, который сказал бы о Ежове плохо. Это был отзывчивый, гуманный, мягкий, тактичный человек».
Летом 1927 года его вызвали в Москву: заведующий организационнораспределительным отделом ЦК Иван Михайлович Москвин предложил ему должность инструктора. Низший в цековской иерархии пост стал для Ежова трамплином. Москвин вскоре сделал его своим помощником, а затем заместителем. Николай Иванович приобрел славу человека, умеющего работать с людьми.
Тогда же Ежов по-новому устроил свою жизнь. С Антониной Алексеевной Титовой разошелся — впоследствии это спасет ей жизнь, ее не тронут. И женился на женщине, с которой познакомился на Кавказе. Для Евгении Соломоновны Хаютиной-Гладун, общительной и веселой женщины, побывавшей с мужем за границей — в Лондоне — и работавшей в журнале «СССР на стройке», это был третий брак.
В ноябре 1930 года Ежов был назначен заведующим распределительным отделом ЦК, стал ведать всеми партийными кадрами страны. Подчинялся он непосредственно Сталину. Отдел вскоре переименовали в отдел руководящих партийных кадров.
Ежов, судя по воспоминаниям, вел себя скромно, казался доступным и приятным человеком, держался весьма демократично, любил выпить и погулять, хорошо пел и сочинял стихи. Бухарин считал его человеком «доброй души». Это потом Ежова назовут «кровавым карликом».
В 1933 году Николая Ивановича назначили председателем центральной комиссии по чистке партии. На XVII съезде избрали заместителем председателя Комиссии партийного контроля, а вскоре он сменил сталинского любимца Лазаря Моисеевича Кагановича на посту председателя Комиссии партконтроля.