В декабре 1937 года на выборах в Верховный Совет СССР депутатами избрали начальников областных управлений, в республиканские Верховные Советы избирали их заместителей. Наркомвнуделы национальных республик и начальники областных управлений НКВД при Ежове превратились в главных людей в стране. Шрейдер вспоминает, что рассказал ему его тогдашний начальник – Станислав Францевич Реденс, свояк Сталина, в 1938 году наркомвнудел Казахстана.

По словам Реденса, после выпивки на даче Ежов разоткровенничался с подчиненными: «Чего вам бояться? Ведь вся власть в наших руках. Кого хотим – казним, кого хотим – милуем. Вот вы – начальники управлений, а сидите и побаиваетесь какого-нибудь никчемного секретаря обкома. Надо уметь работать. Вы ведь понимаете, что мы – это все. Нужно, чтобы все, начиная от секретаря обкома, под тобой ходили. Ты должен быть самым авторитетным человеком в области…»

Если Ежов действительно вел такие разговоры, то о них наверняка сразу же доносили Сталину, которого это могло убедить в том, что нарком внутренних дел – очень неумный человек, раз говорит такие вещи. Никто, даже НКВД, не может быть выше партии…

К началу 1938 года Сталин, вероятно, уже считал, что Ежов свою задачу выполнил. 16 февраля Президиум Верховного Совета СССР присвоил имя Ежова школе усовершенствования командного состава пограничных и внутренних войск НКВД. Наверное, это было приятно Ежову, но подарок был невелик – на сей раз его именем назвали не город, а всего лишь подчиненную ему ведомственную спецшколу. И партийный рост его остановился: в политбюро Ежов так и не был избран, остался кандидатом.

Ежов отправил Сталину рукопись своего труда «От фракционности к открытой контрреволюции» с короткой запиской: «Очень прошу просмотреть посылаемую работу. Это первая глава из книги о «зиновьевщине», о которой я с Вами говорил. Прошу указаний».

Сталину писательские амбиции Ежова, похоже, не понравились. Он не для того назначал Ежова наркомом, чтобы тот писал книги. Книги и без него есть кому писать. Очевидно, Сталин увидел, что и Ежов уже больше думает о своем положении, своем престиже, словом, о своих делишках, вместо того чтобы полностью отдаться делу. Этот вывод не мог не привести к роковым для Ежова последствиям.

Ежов захотел еще и стать ответственным редактором журнала «Партийное строительство». Его самолюбию малограмотного человека льстило сознание, что он теперь вроде как редактирует журнал. И это тоже не могло понравиться Сталину.

В 1938 году Ежов написал в ЦК, Верховный Совет СССР и Верховный Совет РСФСР записку с предложением переименовать Москву в Сталинодар. Хотел услужить хозяину, сделать ему приятное, но не угадал. Сталин этого не захотел: чувствовал, что это будет плохо воспринято. И разозлился на Ежова. Хорошо, когда есть преданный и неутомимый исполнитель, но неумный Ежов стал его раздражать. Сталину нужен был новый человек. Столь же безжалостный, но более толковый.

21 января 1938 года секретарь ЦК Андрей Александрович Жданов выступал в Большом театре на торжественном собрании, посвященном годовщине смерти В.И. Ленина. Он сказал: «1937 год войдет в историю как год, когда наша партия нанесла сокрушительный удар врагам всех мастей, когда наша партия стала крепкой и сильной в борьбе с врагами народа, добившись этого благодаря укреплению нашей советской разведки во главе с Николаем Ивановичем Ежовым».

На самом же деле Ежов уже был не в фаворе.

9 января 1938 года ЦК принял постановление «О фактах неправильного увольнения с работы родственников лиц, арестованных за контрреволюционные преступления».