Несмотря на то, что его бывший патрон Евдокимов имел очень плохие отношения с Ягодой, сам Фриновский числился среди фаворитов наркома. Пользовался он доверием и Сталина, с которым, так же как Евдокимов, был, вероятно, знаком со времени работы в 1920 г. в Особом отделе Юго-Западного фронта.
Ежов познакомился с Фриновским еще до своего назначения в НКВД. Будучи секретарем ЦК, контролирующим органы государственной безопасности, он имел среди руководящих работников наркомата нескольких информаторов, докладывавших ему о ситуации в чекистском ведомстве, о вопросах, обсуждаемых на совещаниях, проводимых Ягодой, и т. д. Одним из таких информаторов был Фриновский.
Летом 1936 г. находившийся в Москве Евдокимов пригласил Ежова и Фриновского к себе в гости. Зашел разговор о чекистских проблемах, и Ежов, рассказав о каких-то делах, высказался в том духе, что если бы он работал в НКВД, то взял бы себе в заместители Фриновского (при этом он дружески похлопал его по плечу), а в аппарат набрал бы людей из северо-кавказского управления{274}.
Став наркомом, Ежов обещание назначить Фриновского своим заместителем выполнил, а теперь уже готов был сделать его и первым замом. Он стал приглашать Фриновского на обед к себе на квартиру, советоваться с ним по делам НКВД, приглашал на совещания по оперативным вопросам, тогда как другие заместители на эти совещания приглашались не всегда.
В одной из бесед, состоявшейся в начале 1937 г., Ежов дал понять Фриновскому, что рассматривает его как наиболее подходящую кандидатуру на должность своего первого заместителя и собирается обратиться с соответствующим ходатайством к вождю. Однако Фриновский не только не обрадовался предстоящему служебному росту, но, напротив, стал всячески отказываться от сделанного ему предложения, объясняя, что почти весь период своей службы в органах госбезопасности провел на командно-строевых должностях в войсках и с оперативно-чекистской работой знаком плохо.
Ежов все это выслушал, но от своего намерения отказываться не стал, и при очередной их беседе, происходившей уже после февральско-мартовского пленума, сообщил Фриновскому о своем окончательном решении выдвинуть его кандидатуру на пост первого заместителя.
В середине апреля 1937 г., вызвав Фриновского к себе на квартиру, Ежов завел с ним разговор о предстоящих кадровых перестановках в НКВД. Затем на беседу были приглашены начальник Секретариата НКВД Я. А. Дейч, начальник Секретно-политического отдела В. М. Курский, заместители Ежова М. Д. Берман и Л. Н. Вельский. Ежов объявил собравшимся о своем решении назначить Фриновского первым заместителем. Тот, по обыкновению, стал отнекиваться, предлагал вместо себя Л. Н. Вельского, однако последний сразу же отказался, после чего все присутствовавшие принялись убеждать Фриновского согласиться занять предложенную ему должность.
Общими усилиями Фриновского удалось уговорить, но тут возникла новая заминка. Начальником Отдела охраны вместо К. В. Паукера, арест которого был предрешен, Ежов предложил присутствующего на встрече В. М. Курского, с одновременным назначением его еще одним своим заместителем. Курский, по примеру Фриновского, стал отказываться, предлагая вместо себя начальника северо-кавказского УНКВД И. Я. Дагина.
Идею назначения Дагина начальником Отдела охраны выдвинул в свое время Евдокимов, поддерживал ее и Фриновский, но Ежов считал, что Дагина в Политбюро еще не знают, а Курский, хорошо зарекомендовавший себя в бытность начальником УНКВД Западно-Сибирского края, партийному руководству известен и, вследствие этого, является более подходящей кандидатурой.
После того, как вопрос о Курском был решен, все остальные кадровые изменения были согласованы достаточно быстро и вступили в силу после их утверждения на ближайшем заседании Политбюро.
Возвышение Фриновского и Курского было всего лишь одним из проявлений начавшейся весной 1937 г. экспансии северокавказского клана чекистов. Сделав ставку на питомцев «гнезда Евдокимова», Ежов стал активно заменять ими прежние ягодинские кадры, в первую очередь на территориальном уровне. Бывший начальник управления НКВД по Северо-Кавказскому краю И. Я. Дагин впоследствии вспоминал: