В 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 года в южном доке началось строительство линкора «Советская Россия».