Скорее всего, эта просьба была удовлетворена, и его отдых и лечение продолжились. И лишь 1 марта 1923 года на заседании оргбюро и секретариата ЦК в Москве (с участием Сталина) Ежов был назначен ответственным секретарем Семипалатинского губкома партии на северо-востоке Киргизской (позднее Казахской) Республики. Хотя сам Ежов на заседании не присутствовал, как это было в 1922 году, Сталин, вероятно, разговаривал с ним по поводу столь ответственного назначения. Ежов получил девять дней отпуска для поездки в Краснококшайск для передачи дел. 9 марта в письме бывшему коллеге по работе в Марийском обкоме партии П.Н. Иванову он писал, что слышал, что "вы убрали Петрова", но к его неудовольствию комиссия оргбюро вновь решила направить Петрова в Марийскую область. Девять дней спустя он написал, что отправляется в Семипалатинск.
Так или иначе, Ежов превратил свой месячный отпуск в полугодовой. Создается впечатление, что в это время он был достаточно слабым функционером, болезненным и неспособным к интенсивной работе. Неудивительно, что о его работе в Марийской области были даны отрицательные отзывы: "Отсутствие достаточной теоретической подготовки и разностороннего организационно-практического навыка не дает возможности тов. Е[жову] сразу ориентироваться в особенно сложной обстановке на руководящем месте. Последнее подтверждается его первыми промахами на первых порах в Маробласти" и как особенность характера было отмечено "некоторое упрямство, иногда граничащее со вспыльчивостью", вытекающее из "его тяги к единоличию". Ввиду недостаточной теоретической подготовки и "малого опыта руководящей работы" не рекомендовалось выдвигать его на вышестоящей должности а использовать на второстепенных ролях - заведующего орготделом или отделом агитации губкома, или же секретарем райкома партии.
Однако к этим рекомендациям явно не прислушались, и 27 марта Ежов подтвердил прибытие в Семипалатинск и приступил к работе в качестве секретаря губкома партии. Как утверждают его биографы, в своей новой должности он опять "проявлял своеволие" по отношению к секретарям райкомов. Фадеев говорит о том, что в некоторых районах преобладали антинэповские настроения. Сторонники уравнительного "коммунизма для бедных" провозгласили независимую "Бухтарминскую Республику" в северо-восточном Казахстане, и Ежов вскоре обнаружил, что "среди руководителей губернии немало скрытых и явных врагов, сочувствующих восстанию и поддерживающих его". Он отправился во взбунтовавшиеся сельские районы без какой-либо военной охраны. Фадеев писал, что эта поездка была трудной и опасной, и мятежники покушались на жизнь Ежова. Но в конце концов мятеж удалось подавить мирными средствами. На фотографии того времени Ежов показан впереди группы солдат, возвращающихся после подавления мятежа.
Примерно через год, в мае 1924 года, Ежов был избран делегатом XIII съезда партии в Москве. В следующем месяце он переводится в Оренбург и возглавляет орготдел Киргизского обкома партии, что, скорее, выглядит понижением в должности, если бы в ноябре того же года он не стал секретарем Киргизского обкома. И здесь он также имел отрицательный опыт работы с местными функционерами. Как позже вспоминал один из бывших заключенных ГУЛАГа, Ежов был настолько неспособен справиться с сильной местной троцкистской оппозицией, что прятался от нее на вокзале в салон-вагоне. В апреле 1925 года Киргизская республика была переименована в Казахскую, а столица перенесена в Кзыл-Орду. Этим же летом Ежов стал заместителем ответственного секретаря Казахстанского крайкома партии и заведующим орготделом. Как указывает Фадеев, он проявил себя непримиримым противником концессий иностранных капиталистов, таких, как британский бизнесмен Лесли Уркарт. Тогда же он самостоятельно изучал марксизм-ленинизм. Фадеев отмечает: "С присущей ему исключительной работоспособностью он ночами сидел над книгами, овладевая теорией Маркса-Ленина-Сталина". В 1924 году в анкете Ежов указал, что знает основную марксистскую литературу. Кроме того, имеются свидетельства, что в течение двух месяцев два раза в неделю по вечерам он посещал занятия кружка марксистского самообразования.
Карьера Ежова продолжалась. В декабре 1925 года он был избран делегатом XIV съезда партии в Москве, завершившего свою работу 31 декабря, а 18 января 1926 года секретариат ЦК известил Казахский обком, что Ежов направляется на годичные курсы марксизма-ленинизма при Коммунистической академии (комакадемии), где готовили профессиональных партийных функционеров. Ежов вернулся в Кзыл-Орду после съезда и 25 января отбыл в Москву, где перед ним открывались новые перспективы для продвижения. Среди тех, с кем он вместе учился, были его будущий ближайший сотрудник Е.Г. Евдокимов и будущий глава Политического управления Красной Армии Л. 3. Мехлис. После того как Ежов завершил обучение в начале 1927 года, в наших сведениях о его деятельности в первой половине этого года появляется пробел. Его российские биографы указывают, что в феврале 1927 года он был назначен инструктором орграспредотдела ЦК ВКП(б). Возможно и то, что в первой половине 1927 года он продолжил свою учебу, или же, как это было после окончания работы в Марийской области, - пассивно ожидал нового назначения, находясь в распоряжении ЦК ВКП(б).
Но точно известно, что в начале июля 1927 года, когда он проходил курс лечения кумысом в санатории в Шафраново неподалеку от Уфы на Урале, орграспредотдел стал разыскивать его в связи с вопросом о его назначении помощником заведующего. Только 13 июля он дал о себе знать, объяснив задержку операцией, которую ему сделали в Уфе. Хотя лечение должно было закончиться лишь 1 августа, он уехал в Москву на следующий день - 14 июля. Оргбюро подтвердило это назначение 15 июля. Назначение на должность произошло необычно быстро. Как сообщает Лев Разгон, именно Иван Михайлович Москвин, заведующий орграспредотделом ЦК с февраля 1926 года, "нашел, достал, вырастил и выпестовал" Ежова: он вызвал "скромного и исполнительного секретаря отдаленного окружкома" в Москву и сделал его последовательно инструктором орграспредотдела, а затем своим помощником и, наконец, своим заместителем. Возможно, Москвин действительно сыграл решающую роль в выдвижении Ежова. Хотя не стоит забывать, что прежде чем получить назначение в орграспредотдел, Ежов был направлен в Москву, как минимум, на годичное обучение. И нет никаких сомнений, что накануне важного назначения он уже был знаком со Сталиным, так как последний считал необходимым хорошо знать своих аппаратчиков, особенно такого уровня.
Ежов стал заместителем заведующего орграспредотделом в ноябре 1927 года. В этом важном качестве он был посвящен в тонкости кадровой политики партии. Его отдел занимался подбором и расстановкой номенклатурных кадров по всей стране и во всех отраслях (сферах деятельности); более того, он осуществлял проверку деятельности партийных организаций на местах. В новой должности он стал делегатом XV съезда партии (декабрь 1927 г.) и XVI партийной конференции (апрель 1929 г.). Авторитет его настолько возрос, что секретарь Татарского обкома партии М.М. Хатаевич летом 1928 года обратился с просьбой, чтобы Ежов заменил его в этой должности: "Есть у вас, в ЦК, крепкий парень Николай Ежов, он наведет порядок у татар…". И хотя в ЦК, вероятно, были согласны с просьбой Хатаевича, по тем или иным причинам новое назначение не состоялось.
В центральной прессе имя Ежова появилось в августе 1929 года как одного из трех авторов - наряду со Львом Мехлисом и Петром Поспеловым - статьи в теоретическом журнале партии "Большевик" под названием "Правый уклон в практической работе и партийное болото". На примере так называемого "астраханского дела", когда "морально-бытовое разложение" партийной верхушки в Астрахани способствовало "усилению частного капитала в рыбной промышленности" и "капиталистические элементы мирно врастали" в систему советского аппарата, авторы доказывали, что "партийное болото" на данном этапе "больше всего переплетается с правым уклоном". Это означает, что наряду с явными правыми уклонистами в партии имелись и скрытые правые уклонисты - "партийное болото". Авторы статьи призывали вести борьбу с характерными проявлениями "партийного болота" - местничеством, делячеством и аполитичностью.
В декабре 1929 года Ежов перешел из орграспредотдела на новую должность - заместителя народного комиссара (наркома) земледелия по кадрам. Наркомом земледелия был Яков Яковлев. Здесь впервые в жизни Ежову пришлось иметь дело с настоящими массовыми репрессиями. Когда в феврале 1930 года служба государственной безопасности - ОГПУ начала аресты и высылки сотен тысяч крестьян, названных "кулаками", то и наркомат земледелия не остался в стороне. В июне-июле 1930 года партийная организация наркомата земледелия выдвинула Ежова делегатом XVI съезда партии.
В нескольких статьях этого периода Ежов подтвердил свой радикализм. В марте 1930 года он опубликовал статью "Город - на помощь деревне" о мобилизации ноябрьским (1929) пленумом ЦК ВКП(б) 25 тысяч рабочих для коллективизации сельского хозяйства - демонстрации, как он указывал, помощи рабочего класса колхозному движению. Другая статья, вышедшая осенью того же года, "Кондратьевщина в борьбе за кадры", была выдержана в духе борьбы с "вредительством в земельных органах" и сельскохозяйственной науке. Отметив недавние заслуги ГПУ в разоблачении вредительской организации в сельском хозяйстве, Ежов призвал бороться со старыми специалистами, в большинстве своем, по мнению автора статьи, - реакционерами. И даже привел любопытные выкладки распределения настроений в профессорско-преподавательском составе сельскохозяйственных учебных заведений. "Советски" настроенных среди них насчитывалось около 30%, аполитичных или нейтральных было 25–30% - их Ежов назвал полюбившимся ему словом "болото", остальные принадлежали к "реакционным группировкам, враждебно настроенным, к советской власти". В статье Ежов утверждал, что необходимо принять серьезные меры к усилению пролетарской прослойки путем "социально-классового подбора" кадров в управленческих и земельных органах, в профессорско-преподавательском составе и среди обучающихся в сельскохозяйственных вузах. По его мнению, в этих организациях оставалось еще немало выходцев из "духовенства, купечества и дворянства". Ежов посчитал одним из методов вредительства проводившуюся старыми спецами линию на универсальное сельскохозяйственное образование, отметив, что именно поэтому "реакционная часть профессуры" выступила против "узкой специализации" вузов, их дробления и передачи в различные ведомства.
В статье, опубликованной в "Правде" в марте 1932 года, "Некоторые вопросы подготовки и расстановки кадров" Ежов продолжал высказывать радикальные взгляды на образование. Он с удовлетворением отмечал, что "ушли в прошлое многофакультетные университеты, оторванные от производства", а их место заняли специализированные высшие учебные заведения, подчиненные хозяйственным наркоматам, неразрывно связанные с производством и способные подготовить инженеров по определенным специальностям за три - четыре года. "Несмотря на сопротивление реакционной части профессуры, - как утверждал Ежов, - 40–45% учебного времени студенты стали проводить на предприятиях и, таким образом, лекционная система все больше и больше уступает место активным методам учебы". Обильно цитируя в этой статье Сталина и Кагановича, Ежов писал: "Наши высшие учебные заведения превращены в своеобразные предприятия, выполняющие заказы народного хозяйства на подготовку необходимых ему специалистов".
Ежов вернулся на работу в партийный аппарат в ноябре 1930 года в качестве главы распредотдела, одного из двух отделов, образовавшихся в результате разделения орграспредотдела. Это была ключевая должность по контролю за подбором и расстановкой партийных кадров. 21 ноября - через неделю после назначения - он был принят Сталиным в Кремле. Тем самым он явно становился допущенным в ближний круг соратников Сталина. Четыре дня спустя по предложению своего непосредственного начальника в аппарате ЦК Лазаря Кагановича Политбюро разрешило ему присутствовать на своих заседаниях и получать все материалы, рассылаемые членам ЦК. Другими словами, Ежов, хотя и не был членом ЦК, получал сведения о государственных и партийных делах наравне с членами Политбюро.
9 ноября 1931 года он снова был принят Сталиным вместе с Кагановичем, Молотовым и Ворошиловым; кроме них, также присутствовали заместитель председателя ОГПУ Генрих Ягода, Э.П. Берзин и С.А. Бергавинов. Два дня спустя Сталин подписал постановление Политбюро о добыче золота на Крайнем Севере. Было решено организовать государственный трест "Дальстрой" под непосредственным руководством Берзина и под контролем Ягоды и установить для треста жесткую программу добычи золота. Бергавинов, в качестве первого секретаря Дальневосточного крайкома партии, должен был изучить возможности использования ледоколов. А Ежов, Ягода и другие должны были "разработать льготы, которыми будут пользоваться как заключенные переселенцы, так и добровольцы за хорошую работу на Колыме (сокращение срока наказаний, восстановление в правах гражданства, обеспечение семей добровольно уехавших, повышение оклада и т.д.)". Так было положено начало печально известной системе принудительного труда на Колыме.
После этой встречи произошел характерный инцидент. Когда Ежов выходил из Кремля вместе с Ягодой и Бергавиновым, Ягода предложил сесть в его автомобиль. По пути Ежов, одетый в легкое летнее пальто, очень сильно замерз. Ягода возмутился, что он так легко одет: как он мог так поступить, если на лечение его слабых легких были потрачены такие значительные средства! Ежов отвечал, что зимнего пальто у него нет. Тогда Бергавинов счел, что в таком случае он должен получить мех на зимнее пальто. В течение двух недель-он получил несколько отрезов беличьего меха, причем без всякого счета. По-видимому, Центральная Контрольная комиссия (ЦКК) узнала об этом, и затем Ежов послал объяснительную записку ее председателю Матвею Шкирятову, утверждая, что мех лежит неиспользованным в его квартире, и он готов поделиться им в любое время.
Этот эпизод следует рассматривать в связи с проблемами со здоровьем Ежова. Еще раньше, в июне 1931 года глава лечебно-санитарного управления (лечсанупра) Кремля доложил Кагановичу и Постышеву, что Ежов страдает туберкулезом легких, мизастенией, неврастенией, вызванной напряженной работой, анемией и недоеданием. Ему требовался немедленный двухмесячный отпуск по болезни в санатории на юге - например, в Абастумани в Грузии или в Кисловодске. В ноябре следующего года он снова сообщил ЦК, что Ежов болен еще и ангиной, а также страдает ишиасом. Ему требуется срочное обследование в Кремлевской больнице и диета, чтобы он мог поскорее вернуться к работе.
В Казани, не позже июня 1921 года, Ежов женился на Антонине Титовой, партийной функционерке низшего звена, которая была на несколько лет моложе его. Она поехала с ним в Краснококшайск и Семипалатинск, но летом 1923 года отправилась в Москву для учебы в Тимирязевской сельскохозяйственной академии. В конце 1925 года супруги воссоединились в Москве. С ними жила и мать Ежова, которой в то время было немногим более 60 лет, и двое детей его сестры Евдокии - подростки Людмила и Анатолий Бабулины, учившиеся в Москве. (Сама Евдокия вместе с 4 другими своими детьми жила в деревне недалеко от Вышнего Волочка Тверской области.) После окончания сельскохозяйственной академии в 1928 году Антонина поступила на работу в наркомат земледелия на должность начальника подотдела. При помощи мужа она опубликовала книгу "Коллективизация сельского хозяйства и крестьянская женщина". Однако примерно в 1930 году они развелись, поскольку Ежов, никогда не отличавшейся супружеской верностью, завязал серьезные отношения с другой женщиной.
Ее звали Евгения Соломоновна (или Залмановна), урожденная Фейгенберг. Она родилась в 1904 году в большой еврейской семье в Гомеле, где ее отец был мелким торговцем. Там же, еще в юном возрасте она вышла замуж за Лазаря Хаютина. Потом она развелась с ним и стала женой журналиста и дипломата Александра Гладуна. С сентября 1926 года они жили в Лондоне, но были высланы из Великобритании в связи с действиями британских властей в мае 1927 года по отношению к советской торговой делегации и последующего разрыва дипломатических отношений между Москвой и Лондоном. Гладун вернулся в Москву, а Евгения стала на некоторое время машинисткой в советском торговом представительстве (торгпредстве) в Берлине, где летом 1927 года она познакомилась с писателем Исааком Бабелем и, возможно, имела роман с ним. По крайней мере, как утверждает вдова Бабеля, писатель знал Евгению еще со времени ее работы в одесском издательстве.
Прошло немного времени, и Евгения вернулась в дом мужа в Москве, а в ноябре 1927 года Ежов, вероятно, впервые появился у нее дома; они могли также встречаться и в санатории на берегу Черного моря. В 1939 году Гладун показал на допросе следующее: "Она называла Ежова восходящей звездой и поэтому ей было выгоднее быть с ним, чем со мной". В 1930 году Ежов женился на Евгении, которая взяла его фамилию. Они жили в центре Москвы. Евгения работала машинисткой в газете "Крестьянская газета", редактором которой был Семен Урицкий, с которым у нее, по-видимому, тоже был роман. Урицкий освободил ее от обязанностей машинистки, желая сделать ее журналисткой. У нее был своего рода салон, где она принимала писателей, артистов и дипломатов. Кроме Бабеля, постоянными гостями салона были писатели Лев Кассиль, Самуил Маршак, а также певец и музыкант Леонид Утесов.