В апреле 1919 года Ежов вступил в Красную Армию. Он служил в батальоне особого назначения в Зубцове, в мае 1919 года оказался в Саратове, где был депутатом местного совдепа и секретарем партячейки военного городка, а в августе поступил здесь же на 2-ю базу радиотелеграфных формирований, которая вскоре переместилась в Казань. Уже 1 сентября Николай Иванович стал переписчиком при комиссаре управления базы. На такую должность вряд ли назначили бы человека с начальным образованием (хотя Ежов скромно писал в анкетах: «грамотен (самоучка!)»). 18 октября последовало повышение — Николая Ивановича сделали комиссаром школы, действовавшей при базе радиотелеграфных формирований.
В январе 1920 года с Ежовым случилась первая в советское время крупная неприятность. Его и начальника школы бывшего подпоручика С. Я. Магнушевского арестовали за то, что они принимали на учебу дезертиров из Красной Армии. На суде, однако, выяснилось, что руководство школы действовало без злого умысла, и, когда Ежов узнал, что курсанты являются дезертирами, он немедленно отослал их в губернский комитет по дезертирам. В результате Магнушевский получил два года тюрьмы с отсрочкой наказания на три года, а Ежов отделался строгим выговором с предупреждением. На карьере Николая Ивановича этот эпизод никак не отразился. В январе 1921 года последовало новое повышение: Ежова назначили комиссаром 2-й базы радиотелеграфных формирований. Но в этой должности он пробыл недолго — лишь до апреля.
В Казани Николай Иванович не ограничивался военной работой. Он был депутатом Казанского Совета рабочих и солдатских депутатов трех созывов и заместителем заведующего агитационно-пропагандистским отделом Кремлевского района Казани. В апреле 1921 года, когда Ежова назначили заведующим этим отделом, он покинул военную службу.
К тому времени наш герой женился на Антонине Алексеевне Титовой, дочери сельского портного. Она родилась в 1897 году в селе Кукмор Казанской губернии. В 1917 году Антонина была студенткой естественного отделения физико-математического факультета Казанского университета, но образование завершить не успела, окунулась в революцию и в 1918 году вступила в партию большевиков. Как и муж, она стала партаппаратчицей, но рангом пониже — работала техническим секретарем одного из райкомов Казани.
Аппаратная работа — вот к чему Николай Иванович чувствовал настоящее призвание. Он был выдающимся бюрократом. Знавшие Ежова по Казани запомнили его исполнительность и безотказность в выполнении любых поручений начальства. Николая Ивановича заметили и начали быстро продвигать вверх по партийной вертикали. В июле 1921-го он стал заведующим агитпропом и заместителем ответственного секретаря Татарского обкома. Но в январе 1922 года Ежов заболел и уехал лечиться в Москву. Здесь в феврале его назначили ответственным секретарем Марийского обкома. Как видно, решили: человек уже работал в Поволжье, в национальном регионе, так что и в проблемах Марийской автономии разберется. А проблемы были — парторганизацию там сотрясали распри между русскими и марийцами. Ежову не удалось погасить конфликт. 15 марта он прибыл в Красно-Кокшайск (ныне Йошкар-Ола), а уже 14 сентября был отозван в отпуск и более в округ не вернулся. Однако неудачу в деле примирения русских и марийских коммунистов ему в вину не поставили.
1 марта 1923 года Оргбюро ЦК рекомендовало Николая Ивановича Ежова ответственным секретарем Семипалатинского губкома. А к октябрю 1925 года он дорос до заместителя ответственного секретаря Казахстанского крайкома. Маленького роста, всего полтора метра, с невыразительной внешностью, Николай Иванович оказался неплохим организатором. Главное же — он всегда держался генеральной сталинской линии и беспощадно боролся со всеми оппозициями.
В 1927 году Ежова взяли на работу в Москву в организационно-распределительный отдел ЦК. Коммунисты Казахстана сохранили о нем самую добрую память. Писатель Юрий Домбровский, прошедший ГУЛАГ и ссылки, встречался в Казахстане с людьми, хорошо знавшими Ежова. Все они отзывались о Николае Ивановиче исключительно тепло. Юрий Иосифович вспоминал: «Три моих следствия из четырех проходили в Алма-Ате… Многие из моих современников, особенно партийцев, с Ежовым сталкивались по работе или лично. Так вот, не было ни одного, который сказал бы о нем плохо. Это был отзывчивый, гуманный, мягкий, тактичный человек… Любое неприятное личное дело он обязательно старался решить келейно, спустить на тормозах… Это общий отзыв. Так неужели все лгали? Ведь разговаривали мы уже после падения «кровавого карлика». Многие его так и называли — «кровавый карлик».
А близко знавший Ежова ссыльный казахский учитель Ажгиреев говорил вдове Бухарина А. М. Лариной: «Что с ним случилось, Анна Михайловна? Говорят, он уже не человек, а зверь! Я дважды писал ему о своей невиновности — ответа нет. А когда-то он отзывался и на любую малозначительную просьбу, всегда чем мог помогал». Но меньше чем за десять лет «добрый человек» превратился в бездушного палача — исполнителя сталинских предначертаний.