На флотах назначение Н. Г. Кузнецова было принято восторженно. «Из Москвы повеяло морским ветром», — говорили между собой военные моряки. «К руководству флотом пришел настоящий моряк, — вспоминал позднее редактор флотской газеты П. И. Мусьяков, — которого мы знали уже не первый год. Он был молод, прошел морскую службу от матроса до командующего флотом, хорошо знал Военно-морской флот, и выбор этот был на редкость удачным».

Военно-морской флот СССР возглавил профессиональный моряк, обладавший необходимыми качествами современного флотоводца: образованностью и кругозором, организаторскими способностями, государственным мышлением и умением видеть новое. Николай Герасимович имел необходимый авторитет на флоте и опыт боевой службы.

Очень доверительные отношения сложились у молодого наркома ВМФ Н. Г. Кузнецова с начальником Главного морского штаба Л. М. Галлером. Лев Михайлович стал не только заместителем наркома ВМФ, а по-существу и наставником адмирала Н. Г. Кузнецова. К его советам молодой флотоводец всегда прислушивался. «Надо использовать „медовые“ месяцы, — учил Л. М. Галлер, поглаживая свои рыжеватые усы. — В первое время ваши предложения будут рассматривать быстро. И быстро будут принимать по ним решения. Потом станет труднее…» Этот прогноз адмирала, умудренного жизненным опытом, полностью оправдался.

Прежде всего необходимо было быстро решать вопросы строительства «большого» Военно-морского флота. Читателю, я думаю, будет интересно знать, предысторию этой непростой проблемы.

В ноябре 1926 года Совет труда и обороны (СТО) СССР утвердил «Шестилетнюю программу строительства Морских Сил РККА на 1926–1932 гг.». А уже в марте-апреле 1927 года были заложены шесть подводных лодок, позднее началось строительство восьми сторожевых кораблей. В июле 1927 года решением Реввоенсовета началось строительство 24 торпедных катеров и четырех подводных лодок. Ремонт линкора «Фрунзе» и достройка крейсера «Ворошилов» из-за нехватки финансовых средств были отложены. 11 июля 1933 года СТО принял постановление «О программе военно-морского строительства на 1933–1938 гг.», а уже в ноябре она была переименована в «Программу кораблестроения на вторую пятилетку». В ней предусматривалось строительство 875 боевых кораблей большинства классов, в том числе и легких крейсеров. Несмотря на колоссальные усилия судостроителей, программа по военному кораблестроению как первой, так и второй пятилеток в полном объеме не была выполнена. Объективных причин невыполнения планов было немало: не хватало опытных конструкторов, инженеров, квалифицированных рабочих, слабы были еще производственные мощности судостроительных заводов.

В 1936 году СССР обладал самой крупной и мошной в Европе армией. И. В. Сталин принял решение начать крупномасштабное строительство Военно-морского флота. В 1935 году под руководством начальника Морских Сил РККА В. М. Орлова, его первого заместителя И. М. Лудри, начальника Главсудпрома Р. А. Муклевича началась работа по выбору типов кораблей для будущего флота. Разработку программы кораблестроения активно поддерживал Маршал Советского Союза A. И. Егоров. 26 июня 1936 года СНК СССР утвердил кораблестроительную программу, которая включила строительство 24 больших и малых линкоров, 20 легких крейсеров, 17 лидеров эсминцев, 128 эскадренных миноносцев, 344 подводных лодок. Укреплялась производственная база судостроения в Ленинграде и Николаеве. В 1936 году началось строительство судостроительного завода в Комсомольске-на-Амуре, а 1939 году — в Молотовске (ныне Северодвинск), недалеко от столицы Русского Севера — Архангельска.

30 декабря 1937 года «в целях дальнейшего укрепления морских рубежей Советского Союза» ЦИК и СНК СССР приняли постановление о создании Наркомата Военно-морского флота, который наделялся собственным бюджетом, фондами заготовок материальных средств, планом заказов промышленности. Военные моряки получили большую самостоятельность в определении перспектив развития флота. До этого времени ВМФ был представлен в Наркомате обороны Управлением Морских Сил РККА, начальником которого был с 1931 по 1937 год флагман флота 1-го ранга B. М. Орлов.

Первым наркомом ВМФ стал П. А. Смирнов. С высоты сегодняшнего дня вряд ли наличие двух наркоматов в составе Вооруженных сил СССР можно считать наилучшим вариантом организационного строительства.

15 января 1938 года на объединенном заседании палат Верховного Совета СССР председатель СНК СССР В. М. Молотов, курирующий в Политбюро ЦК ВКП(б) флот, обнародовал новую концепцию военно-морской политики государства: «У могучей Советской державы должен быть соответствующий ее интересам, достойный нашего великого дела морской и океанский флот».

В то же время в 1937–1938 годах руководство Военно-морского флота было обезглавлено. Участники разработки строительства «большого флота» В. М. Орлов, И. М. Лудри, П. И. Смирнов-Светловский, Г. А. Муклевич, А. И. Егоров были арестованы, а затем расстреляны.

Попали в число «врагов народа» флагман флота 1-го ранга М. В. Викторов, командующие флотами, флагманы флота 2-го ранга И. К. Кожанов, К. И. Душенов, Г. П. Киреев. Практически все командующие флотами и флотилиями и многие их заместители ушли в то время «пить кофе» к Лаврентию Павловичу. В те зловещие годы «пить кофе» у Берии означало быть арестованным. Всего с мая 1937 года по сентябрь 1938 года на флоте было отправлено в тюрьмы, этапировано в лагеря, расстреляно более трех тысяч человек командно-политического состава ВМФ. К репрессиям активно приложили руку бывшие наркомы П. А. Смирнов и М. П. Фриновский.

Всеобщее уважение среди военных моряков флотоводец Н. Г. Кузнецов завоевал тем, что в годы репрессий умел постоять за подчиненных, спасти их от верной гибели. Благодаря его вмешательству был освобожден из лагеря командир 5-й бригады Тихоокеанского флота Г. Н. Холостяков (впоследствии вице-адмирал). Адмирал в отставке С. Г. Захаров вспоминал, что Н. Г. Кузнецов многое сделал для того, чтобы Военная коллегия Верховного суда СССР пересмотрела дела командиров флота, осужденных якобы за вредительство и шпионаж. И не случайно среди военных моряков укрепилось мнение о наркоме ВМФ как о мужественном и «на редкость порядочном человеке».

Первые наркомы ВМФ в силу различных причин были не способны развернуть крупномасштабное строительство флота. Адмиралу Н. Г. Кузнецову досталась нелегкая задача реализации довоенной кораблестроительной программы и подготовки флота к войне. Он, как мог, исправлял ошибки своих предшественников. К примеру, была решительно отклонена разработка легкого торпедного катера. В 1939 году конструкторы разработали проекты принципиально новых мореходных катеров типа «Комсомолец» и до начала войны наладили их серийное производство. В октябре 1939 года по представлению Н. Г. Кузнецова и И. Ф. Тевосяна были утверждены основные элементы новой серии эсминцев.

Для обеспечения боевыми кораблями Северного флота создавалась новая строительная база близ Архангельска. Началось строительство мощного судостроительного завода № 402. Проектная численность судостроителей устанавливалась в количестве 20 тысяч человек. Днем рождения Северного машиностроительного предприятия является 21 декабря 1939 года — день закладки первого линкора «Советская Белоруссия». 22 июля 1940 года в южном доке началось строительство линкора «Советская Россия».