Кузнецов получил назначение на должность старшего помощника командира нового крейсера «Красный Кавказ». За год команда корабля превратилась в дружный, сплоченный коллектив, способный четко действовать в любых сложных условиях обстановки. В 1933 году крейсер вошел в состав боевого ядра Черноморского флота.
В ноябре 1933 года капитан 2-го ранга Кузнецов назначается командиром крейсера «Червона Украина». В этой должности он пробыл до 15 августа 1936 года. Став командиром крейсера, Николай Герасимович прежде всего начал отрабатывать организацию корабельной службы. Ломая сложившийся на флоте стереотип сезонной боевой подготовки, он уже в марте выводил крейсер в море, отрабатывая навыки плавания в любых погодных условиях. Им была разработана система боевой готовности одиночного корабля; позднее она была принята на всех флотах СССР. Экипаж крейсера приобрел навыки стрельбы орудий главного калибра на самых больших скоростях хода крейсера и на предельной дистанции обнаружения цели. Впервые артиллеристы стали использовать самолет для корректировки невидимой цели. Вскоре на флоте стали говорить о новом методе подготовки экипажа «по системе Кузнецова».
В 1935 году крейсер «Червона Украина» занял первое место в Морских Силах СССР. За успехи крейсера на учениях Н.Г.Кузнецов был награжден орденом «Знак Почета».
В том же году Н.Г. Кузнецов был удостоен ордена Красной Звезды «за выдающиеся заслуги в деле организации подводных и надводных Морских Сил РККА и за успехи в боевой и политической подготовке краснофлотцев».
В августе 1936 года Н.Г.Кузнецов назначается военно-морским атташе и главным военно-морским советником, а также руководителем советских моряков-добровольцев в Испании. Им много было сделано для того, чтобы республиканский флот выполнил поставленные задачи. Его деятельность по оказанию помощи республиканскому флоту была высоко оценена советским правительством: в 1937 году он был награжден орденами Ленина и Красного Знамени.
Вернувшись из Испании, 35-летний капитан 1-го ранга получил назначение на должность заместителя командующего Тихоокеанским флотом и с присущей ему энергией стал изучать специфику одного из самых молодых флотов страны. Основу будущего флота должны были составить подводные силы и морская авиация. Самой большой проблемой, с которой пришлось столкнуться Кузнецову, была нехватка командных кадров, вызванная массовыми репрессиями в армии и на флоте. Ему самому меньше чем через год пришлось принять командование флотом, так как бывший командующий Г.П.Киреев был арестован в Москве в конце 1937 года. Николай Герасимович был в должности командующего Тихоокеанским флотом с 10 января 1938 по 28 марта 1939 года.
На Дальнем Востоке было неспокойно. Японцы господствовали на море и стремились к захвату новых территорий. В состав флота Японии входили 10 авианосцев, 10 линкоров, 35 крейсеров и более 100 эсминцев. Советский Тихоокеанский флот имел примерное равенство с японцами только по подводным лодкам, в остальных видах кораблей он явно уступал. Дальневосточное побережье было практически не защищено, и японское командование могло высадить военные силы в любой точке.
Неотложными задачами нового командующего стали строительство береговых батарей и усиление морской авиации. В ряде пунктов велось усиленное строительство аэродромов и военных городков. Город Владивосток – главная база флота – был оборудован мощными береговыми батареями и авиационным прикрытием, в строй входили новые корабли, укреплялись морские и сухопутные границы, были проведены учения по взаимодействию флота и армейских частей в местах наиболее возможной высадки войск противника.
В декабре 1937 года постановлением ЦИК и СНК СССР был создан Наркомат ВМФ СССР; в марте 1938 года Н.Г.Кузнецов был введен в состав Главного военного совета ВМФ при Наркомате ВМФ.
В июле 1938 года японские войска перешли границу на юге Приморья, возле озера Хасан, стремясь захватить сопки Заозерную и Безымянную, так как с них открывалась прямая дорога на Владивосток. Здесь развернулись ожесточенные бои с большими потерями с обеих сторон. Кузнецов лично выезжал в район боевых действий, а флот непрерывно перебрасывал к местам сражений военные части и грузы и вывозил раненых.
Ожидая нападения японского флота с моря, Николай Герасимович отдал приказ подводным силам занять позиции на возможных путях движения японских кораблей. Торпедные катера также находились в боевой готовности.
28 марта 1939 года Н.Г.Кузнецов был назначен заместителем наркома ВМФ, а 28 апреля 1939 года – народным комиссаром ВМФ.