Отозвали Кузнецова осенью 1937 года, за заслуги наградили орденами Ленина и Красного Знамени. На должности, требовавшей не только знаний, но и дипломатического искусства, моряк пользовался уважением и своих товарищей, и испанцев. Однако энергичные и знающие специалисты требовались и в СССР. После многочисленных арестов 1937 года в высшем командовании освободились должности разных уровней. С августа 1937 года Н.Г. Кузнецов — первый заместитель командующего, затем, с 10 января 1938 по 28 апреля 1939 года, — командующий Тихоокеанским флотом. В начале командования он был всего капитаном 1?го ранга, позднее — флагманом 2?го ранга. Кузнецов не имел опыта командования соединением, но учился на ходу. Не много проводя времени в кабинете, молодой флотоводец бывал в частях и на кораблях, объехал огромное пространство Дальнего Востока, вникал в суть службы, добивался от командиров досконального знания театра военных действий и возможностей противника.
В период двухнедельного конфликта на озере Хасан, когда возникла опасность для Владивостока, Кузнецов изыскивал способы взаимодействия флота с наземными войсками. Ожидая воздушный налет на Владивосток, командующий организовал полномасштабные учения по затемнению, которые выявили недостатки готовности базы и флота. Готовность к нападению — этот вопрос надолго стал важнейшим для Кузнецова. Так как флот — это не только корабли, но и многочисленные береговые службы, верфи и т. п., потребовалось обеспечить всеобщую их подготовку на случай войны. Уже с начала 1938 года Кузнецов организовал тренировки «Тыловое обеспечение боевых операций». Штаб флота разработал систему ступенчатой готовности, которая со временем приобрела всефлотский характер.
Кузнецова заметили в столице. 28 марта И.В. Сталин предложил флагману 2?го ранга работу в Москве. С марта 1939 года Кузнецов — заместитель наркома ВМФ, с 28 апреля 1939 года — нарком ВМФ.
Уже в первый день руководства наркоматом Кузнецов потребовал от подчиненных жить нуждами флота и знать все о нем в своей сфере деятельности, уменьшить бюрократическую переписку. Нарком распорядился воссоздать на кораблях кают?кампании как место отдыха и воспитания командиров.
Так получилось, что моряку досталась нелегкая ноша подготовки к войне с Германией, которую он считал неизбежной, и руководство флотом в ходе самой тяжелой из войн истории.
Не хватало специалистов после репрессий 30?х годов. Не существовало документа, регламентировавшего взаимоотношения наркоматов обороны и ВМФ. Строилось немало кораблей, однако основные средства шли на линкоры и крейсера, тогда как мало уделяли внимания противолодочным и тральным судам, зенитной обороне кораблей. Система базирования и организация флота отставали от роста его численности. Потому 25 июля 1940 года, представляя трехлетний план кораблестроения (1940–1942), Кузнецов отметил несбалансированность в развитии сил флота. Лишь 19 октября 1940 года ЦК ВКП(б) и СНК СССР решили пересмотреть программу в пользу легких сил. Однако до начала войны устранить диспропорции не удалось.
Уже через несколько месяцев после вступления в должность наркома Кузнецов ввел в действие трехстепенную систему оперативной готовности флота. По этой системе готовность № 3 предусматривала поддержание обычной службы при повышенном внимании. При готовности № 2 корабли принимали все запасы, увольнение сокращали до минимума. По готовности № 1 все корабли и части могли немедленно действовать.
Не всегда наркому удавалось добиваться решений, нужных для развития морских сил. Со временем, получив опыт, Кузнецов все чаще спорил по кардинальным вопросам развития флота, даже если его возражения вызывали недовольство И.В. Сталина.
Кузнецов в качестве наркома ВМФ участвовал в переговорах с Англией и Францией. Он был искренне уверен, что при конструктивном подходе государства могли выступить единым фронтом против фашизма. Заключенный с Германией договор о ненападении он считал только средством получить отсрочку, необходимую для перевооружения, и был уверен, что Гитлер непременно нападет на Советский Союз. В декабре 1940 года под руководством Кузнецова были проведены сборы высшего комсостава ВМФ, посвященные изучению опыта первого года мировой войны в Европе и войны с Финляндией, определены недостатки и выработаны пути их исправления. В конце 1940 года вступило в силу «Временное наставление по ведению морских операций».