Были даже введены в употребление специальные бланки для приказов с заголовком «Объединенный Приказ НКВД СССР и Наркомата Водного Транспорта»{587}. Хотя Ежов и утверждал, что два первых месяца после своего нового назначения заходил в НКВД только урывками, он продолжал серьезно вникать в его дела. Когда в апреле-мае в НКВД проводилась реорганизация структуры центрального аппарата, Ежов не смог остаться в стороне. Так, 28 мая, через две недели после самоубийства В.А. Каруцкого — преемника Заковского на посту главы Московского НКВД, он присутствовал на совещании оперсостава У НКВД по Московской области и представил московским чекистам нового начальника и своего ставленника В.Е. Цесарского. Было много подобных дел, требующих его внимания, тем более что он был недоволен администрированием Фриновского, который, как Ежов писал Сталину, «никогда не был полноценным заместителем». В частности, Фриновский неохотно проводил чистку аппарата НКВД: «Однажды раздраженно в присутствии многих, и Фриновского в том числе, я потребовал личные дела сотрудников тогдашнего 4-го отдела чтобы заняться этим самому. Конечно, из этого ничего не вышло. Опять запарился во множестве текущих дел, а личные дела сотрудников продолжали лежать»[62].

Ежов прилагал много усилий к выдвижению сотрудников НКВД на ключевые позиции в правительственном и партийном аппарате{588}. Так, например, в середине 1938 года в высшие звенья регионального партийного руководства были переведены главы региональных НКВД, в том числе шеф Омского НКВД К.Н. Валухин (возглавил Свердловский обком 27 апреля) и шеф Кировского НКВД Л.П. Газов (возглавил Краснодарский крайком в мае){589}. Другие его ставленники попали в правительственный аппарат. Разумеется, все эти назначения проводились с согласия Сталина и утверждались Политбюро. При определенных условиях такое положение дел могло бы насторожить Сталина, но он закрывал глаза на происходящее и не ставил под сомнение усердие и преданность Ежова. Хотя и тени сомнения достаточно, чтобы вызвать у него подозрения и обвинить Ежова в сознательном продвижении своих людей с целью захватить власть. 

В середине июня Ежов был сражен известием, что начальник Дальневосточного управления НКВД Г.С. Люшков, испугавшись ареста, 13 июня перебежал к японцам, перейдя границу с Манчжурией{590}. Бывший заместитель главы секретно-политического отдела ГУГБ в августе 1936 года был назначен начальником управления НКВД Азово-Черноморского края, а в конце июля следующего года был перемещен на должность начальника управления НКВД Дальневосточного края (конечно, не без ведома и напутствия Сталина, который принял его за несколько дней до назначения){591}. У Ежова, хорошо знавшего Люшкова с 1933–1934 годов, были причины тревожиться, так как его могли заподозрить в потворстве Люшкову. Позднее Фриновский показал, что летом 1937 года из НКВД Грузинской ССР прислали показания Т.И. Лордкипанидзе о принадлежности Люшкова к «заговорщикам Ягоды», о том же сказал на допросе и сам Ягода. Ежов не только скрыл эти улики от Центрального Комитета, но и назначил Люшкова на руководящую должность в НКВД Дальнего Востока. Более того, он поручил Фриновскому еще раз допросить Ягоду, чтобы выгородить Люшкова. Понимая, что от него требуется, Ягода показал, что Люшков в заговоре не участвовал{592}.

О показаниях Л.Г. Миронова и других свидетелей о заговорщической деятельности Люшкова тоже не было доложено. Правда, сам Люшков был обо всем поставлен в известность, и в январе 1938 года во время приезда в Москву на сессию Верховного Совета он возмущенно жаловался Фриновскому на недоверие и слежку. Фриновский заверил его, что и он, и Ежов «пытаются уберечь его», хотя на самом деле Фриновский хотел арестовать Люшкова. Ежов был не согласен, опасаясь, что выплывет обман с показаниями против Люшкова. Вместо этого он поручил Фриновскому сказать Люшкову, чтобы в крайнем случае тот покончил с собой. Условным знаком должна была быть телеграмма из Москвы о его отставке или назначении в Москву либо повышении в звании{593}. В марте или апреле 1938 года на повторном допросе Миронова Ежов принудил его отречься от показаний против Люшкова. Приблизительно в это же время, 16 апреля, заместителя Люшкова М.А. Кагана вызвали в Москву и по прибытии арестовали. По словам Фриновского, это было сигналом Люшкову покончить с собой, но тот не отреагировал. Повторным сигналом была телеграмма, посланная Люшкову Ежовым в конце мая 1938 года, в которой сообщалось о его назначении в Москву, в центральный аппарат НКВД. Но Люшков вместо самоубийства сбежал в Японию{594}. Позднее на суде Ежов утверждал, что хотел арестовать Люшкова, но тот вовремя сбежал{595}.

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

Вечером 15 июня, через три дня после побега Люшкова, Фриновский в кабинете Ежова встретил командующего Дальневосточной армией маршала В.К. Блюхера. Блюхер хотел разузнать о массовых операциях и о Люшкове. Он также пытался выяснить, как к нему относятся, поскольку существовало подозрение, что он связан с «военно-фашистским заговором». Ежов не успел с ним побеседовать, он был вызван в Центральный Комитет. Фриновский и Блюхер немного его подождали, а потом им было сказано, что Ежов будет не скоро. Фриновский тем временем сказал Блюхеру, что через два дня сам собирается на Дальний Восток{597}. Так совпало, что накануне было вынесено решение о поездке Фриновского. Ежов либо улучил момент и виделся со Сталиным в промежутке с побега Люшкова до встречи с Блюхером вечером 15 июня, либо решение было принято во время его телефонного разговора со Сталиным. Как бы то ни было, 17 июня по поручению Политбюро Фриновский уехал на Дальний Восток вместе с начальником Главного политического управления Красной Армии Львом Мехлисом. Они получили широкие полномочия разобраться в подробностях побега Люшкова и провести широкомасштабные аресты. Перед отъездом Фриновский и Мехлис отослали директиву краевому НКВД и спецотделам армии и флота, чтобы в течение недели была проведена подготовка к «массовой операции по устранению право-троцкистских военно-фашистских элементов, агентов японской и других разведслужб, бывших белогвардейцев, антисоветских элементов из бывших партизан, попов и раскольников, всех немцев, поляков, корейцев, латышей, финнов и эстонцев, подозреваемых в шпионаже». По прибытии Фриновский провел массовые аресты. Кроме того он установил скрытое наблюдение за Блюхером и посылал в Москву отчеты о слежке. 22 октября 1938 года по приказу Ежова, согласованному с Берией, Блюхер был арестован. Фриновский вернулся в Москву только после 22 августа, к этому времени Берию уже назначили первым заместителем Ежова{598}.