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