Свой вклад в решение кадровых вопросов наркомата внес и Сталин. По его инициативе первым заместителем Ежова в Наркомводе был назначен отец-основатель «северокавказской школы» чекистов Е. Г. Евдокимов, работавший на тот момент первым секретарем Ростовского обкома партии.

К этому времени звезда Евдокимова уже закатилась. Серьезные проблемы возникли у него еще осенью 1937 г., в связи с заявлениями, поступившими в ЦК ВКП(б), Комиссию партийного контроля, редакцию «Правды», в которых рассказывалось о его связях с репрессированными «врагами народа» — бывшим заместителем наркома путей сообщения Я. А. Лившицем, бывшим председателем Северо-Кавказского крайисполкома И. Н. Пивоваровым и другими, в результате чего политическая репутация Евдокимова была основательно подпорчена.

В начале ноября 1937 г. Сталин направил в Ростов на должность второго секретаря обкома партии своего давнего помощника, заместителя заведующего Особым сектором ЦК ВКП(б) Б. А. Двинского. Евдокимов по-прежнему оставался первым секретарем обкома, однако всем вскоре стало ясно, что хозяином положения он уже не является.

Сам Евдокимов, вероятно, наиболее отчетливо осознал этот факт, когда назначенный незадолго до этого начальником местного УНКВД Я. А. Дейч (сам, кстати, бывший северокавказец) стал собирать материалы на лиц из его ближайшего окружения, а затем и арестовывать некоторых из них.

Евдокимов пожаловался Ежову и Фриновскому. На первых порах они ничего не предпринимали, сами, вероятно, не зная, как себя вести в создавшейся ситуации. Но определяться все же пришлось. Произошло это после того, как Дейч получил от кого-то из арестованных показания на Евдокимова, как на участника антисоветского подполья, и прислал их Ежову. Бывший нарком внутренних дел Украины А. И. Успенский вспоминал позднее:

В конце января 1938 г. Дейч был отстранен от занимаемой должности, и на его место назначен начальник иркутского УНКВД Г. А. Лупекин.

Однако и при новом руководителе ростовских чекистов ситуация лучше не стала. До начальства в Москве было далеко, а посланец Сталина Двинский — рядом, и, решая, кому из них опаснее не угодить, Лупекин сделал тот же выбор, что и Дейч.

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

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

Конечно, Ежов предпочел бы в качестве первого заместителя в НКВТ иметь человека, разбирающегося в проблемах водного транспорта, однако переубедить Сталина ему не удалось, и 3 мая 1938 года назначение Евдокимова было утверждено решением Политбюро.

Приехав в Москву, Евдокимов первым делом попросил Ежова помочь реабилитировать себя в глазах Хозяина. Рассказав о том, как ростовские чекисты арестовывают невинных людей и создают душе дела, он предложил Ежову передопросить подследственных, давших на него показания, и убедиться, что все их обвинения в его адрес являются вымыслом.

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

Евдокимова нужно было выручать, и с этой целью Ежов посылает в Ростов для проверки деятельности местного УНКВД бригаду чекистов во главе со своим верным соратником М. И. Литвиным, незадолго до этого назначенного начальником ленинградского управления.

Задача, стоящая перед Литвиным, была не очень сложной. Г. А. Лупекин был известен в НКВД как закоренелый «липач», так что профессионалам, хорошо знакомым с технологией следственной работы, не составило труда доказать, что и в данном случае речь идет об откровенной фальсификации.

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

После того как первоочередные кадровые проблемы Наркомвода были в основном решены, перед Ежовым с неизбежностью встал вопрос, что же делать дальше, как преодолеть хроническое отставание отрасли, ведь одного только подтягивания производственной дисциплины и сурового наказания нерадивых работников было явно недостаточно. Нужно было при том же уровне финансирования, качества рабочей силы, изношенности оборудования и т. д. найти способ в кратчайший срок резко повысить эффективность труда водников.

В принципе, такой способ в Советском Союзе был к этому времени уже изобретен, и назывался он стахановским движением по имени донецкого шахтера А. Г. Стаханова, перекрывшего в одну из смен в августе 1935 года норму добычи угля отбойным молотком в 14 раз. Уже в ноябре того же года состоялось всесоюзное совещание стахановцев промышленности и транспорта, на котором почин Стаханова получил высокую оценку Сталина, заявившего, что именно на этом пути страна сможет достигнуть такого уровня производительности труда, который необходим для перехода от социализма к коммунизму.

С тех пор стахановцы появились во всех отраслях народного хозяйства. Были они и в Наркомводе, правда, такой всесоюзной известности, как у самого А. Г. Стаханова или у его последователей — железнодорожника П. Ф. Кривоноса, ткачих сестер Виноградовых и некоторых других, они не имели. А между тем отрасль явно нуждалась в лидере, способном возглавить стахановское движение на водном транспорте, подняв его на качественно новый уровень.

И такой человек нашелся. 20 мая 1938 года в газете «Водный транспорт» было опубликовано открытое письмо Ежову от слушателя Академии водного транспорта А. Ф. Блидмана, который уже долгое время занимался совершенствованием работы погрузочных транспортеров и в данный момент проверял в Днепропетровском порту одну из своих идей. В письме говорилось:

Далее в письме указывалось, что эти успехи — результат огромного внимания, которое уделяет партия и правительство водному транспорту. «Назначение Вас народным комиссаром, — продолжал Блидман, — воодушевило всех водников, подняло нас на большие деда, на борьбу за превращение водного транспорта в передовую отрасль (народного хозяйства)». Заканчивалось письмо обещанием драться за еще более высокую производительность транспортеров, приложить все силы, все умение, чтобы передать новые методы работы широким массам водников.

Суть метода заключалась в следующем. В соответствии со сложившейся практикой груз на транспортеры доставлялся грузчиками вручную, и от того, как быстро они это делали, зависела скорость погрузки. Блидман заменил грузчиков тремя дополнительными транспортерами, расположенными так, что в процессе работы уголь из уложенных на берегу высоких конусообразных куч ссыпался на них самотеком за счет угла естественного откоса. Поскольку на основной транспортер поступало теперь гораздо больше угля, Блидман увеличил мощность его мотора, в результате чего скорость движения ленты возросла в 4 раза. Были внесены и другие изменения в организацию труда, заранее созданы все условия, необходимые для ударной работы, что и позволило добиться такого высокого результата.