В конце 1937 года создан был Народный комиссариат Военно-Морского Флота СССР. Это явилось важным событием. Советский военный флот быстро рос, пополнялся новыми кораблями. Партия и правительство приняли обширную программу превращения нашей страны в сильную морскую державу, как и приличествует государству, берега которого омывают полтора десятка морей и два океана. Закладывались линкоры, крейсеры, эсминцы, подводные лодки. Все бы хорошо, да вот беда: руководство наркомата менялось по разным причинам с непостижимой быстротой. Трудно было даже запомнить фамилии наркомов и их заместителей. И еще удивительно было, что морскими наркомами становились не люди флота, а пришельцы «со стороны», как правило, мало смыслившие в морских делах. В этом Николай Герасимович убедился, когда его вызвали в Москву на заседание Главного морского Совета. Едва Кузнецов приехал, его принял новый Нарком ВМФ М. П. Фриповский. Фамилию эту Николай Герасимович прежде не слышал. Вполне естественно: как выяснилось, раньше Фриновский работал совсем в другом ведомстве, в НКВД, занимался там вопросами пограничной охраны. В ходе беседы Николай Герасимович с грустью убедился, что о Военно-Морском Флоте нарком имеет весьма смутное представление.
На заседании Главного морского Совета речь шла о развертывании большого океанского флота, об освоении новых кораблей, о создании нового боевого устава Военно-Морских Сил, о других важных проблемах. Люди, приехавшие с флотов, обсуждали все это не спеша, вдумчиво, с чувством своей ответственности… А потом вдруг события понеслись с нарастающей быстротой, наслаиваясь одно на другое.
Состоялась встреча руководителей флота со Сталиным. В Грановитой палате был дан обед. Были речи и тосты, вдохновлявшие моряков, призывавшие их к новым свершениям. Прямо с приема Николай Герасимович отправился на Ярославский вокзал. Девять суток провел в удобном купе международного вагона. Читал деловые бумаги, художественную литературу, любовался зимними пейзажами, не переставая восхищаться величием и красотой российских просторов.
Во Владивостоке чувствовалось приближение весны (город расположен на широте Крыма). Пригревало солнце. Корабли готовились к летней кампании. А Николай Герасимович, едва осмотревшись в своем обширном хозяйстве, начал опять собираться в дорогу — на XVIII съезд партии большевиков.
Открылся съезд 10 марта 1939 года в Большом Кремлевском дворце. Совершенно неожиданно для Николая Герасимовича его избрали в президиум. Подумал: наверно, это связано с хасанскими событиями, взволновавшими всю страну. Но удивительно все же: нарком Фриновский в зале, в одиннадцатом ряду, а комфлота — на сцене… Более того, Кузнецову предложили выступить. С самой высокой трибуны в стране. Николай Герасимович торопливо набросал тезисы. И разволновался, услышав:
— Слово имеет Шолохов. Приготовиться Кузнецову.
Сказать-то ему было о чем, важно только успокоиться, взять себя в руки. Суть выступления: замыслы японских милитаристов и готовность Тихоокеанского флота к отражению возможной агрессии. Слушали военного моряка с большим вниманием.
В перерыве к Кузнецову подошел Сталин, протянул бумагу:
— Прочтите.
Это был рапорт Фриновского, который просил освободить его от обязанностей наркома, ссылаясь на «незнание морского дела».
— Вам понятно? — спросил Сталин и круто повернулся, не дожидаясь ответа.
Николая Герасимовича избрали членом Центрального Комитета ВКП (б). Он намеревался скорее вернуться на флот, но его попросили задержаться пока в Москве. Среди ночи раздался телефонный звонок. Кузнецова вызывали в Кремль. Машина ждала у подъезда. Короткая беседа со Сталиным, и новое назначение: Николай Герасимович стал первым заместителем наркома ВМФ.
Ситуация сложилась странная: первый заместитель есть, но наркома-то нет. А жизнь не стояла на месте, требовалось решать множество разных вопросов. Росла гора бумаг на столе наркома. Николай Герасимович поехал к Андрею Александровичу Жданову, который занимался в ЦК флотскими делами. Поинтересовался, как поступать.
— Решайте сами, — ответил Жданов. — По наиболее крупным и сомнительным вопросам звоните мне. Поможем.
Николай Герасимович тогда не понимал даже, доволен ли он новой должностью, по душе ли ему новые обязанности? Слишком неожиданным все было, не оставалось времени основательно обдумать свое положение. Только начал с помощью начальника Главного морского штаба Льва Михайловича Галлера знакомиться со структурой наркомата, с людьми — еще один поворот: Жданов сообщил, что ему и Кузнецову предложено выехать в Хабаровск и Владивосток для подготовки некоторых постановлений. В том числе определить, насколько пригодна для строительства нового порта бухта Находка.