Наркомату ВМФ в течение всей войны приходилось действовать «по обстановке», максимально активизируя работу в период наиболее крупных и важных сухопутных стратегических операций. Так, в июле 1943 года, в связи с началом битвы на Курской дуге, Кузнецов дал на флоты шифровку: «Учесть обстановку и в пределах поставленных оперативных задач повысить свою боевую активность, приковывая силы противника к побережью и этим помогая частям Красной Армии в кратчайший срок парализовать попытки противника к наступлению». Возможно, в масштабе грандиозной Курской битвы вклад ВМФ в ее победный исход был не слишком заметным, но он был.
В целях улучшения организации службы приказом наркома ВМФ 17 июля 1943 года был введен в действие новый «Корабельный Устав Военно-Морского Флота СССР», состоящий из двух частей: «Боевая служба корабля» и «Повседневная служба корабля». Устав был весьма удачным и без существенных изменений просуществовал до 1951 года.
На протяжении всего 1943 года Кузнецов продолжал лично сотрудничать и общаться с представителями союзнических военно-морских миссий в СССР, решая и согласовывая с ними множество вопросов — от организации проводки и охраны конвоев, передачи боевых кораблей до таких, казалось бы, мелких (но притом очень важных) вопросов, как перевод на русский язык инструкций по эксплуатации английской и американской военной техники. Приобретя в таком общении определенный опыт, Кузнецов стал проявлять себя как настоящий дипломат. Наглядный тому пример: 18 августа 1943 года посол США в СССР адмирал У. Стэндли, кэптен Дункан и его заместитель коммандер М. Аллен встречались с Кузнецовым. Нарком ВМФ рассказал немало нового о советских Северном и Тихоокеанском флотах, предупредив, что «данная информация не должна передаваться британским королевским ВМС». Видимо, уже тогда он ощущал разные векторы в политике СССР по отношению к союзникам.
Едва в 1943 году произошел стратегический перелом, Сталин немедленно вернулся к идее усиления ВМФ. В конце 1943 года Кузнецов представил ему двухгодичный план проектирования новых кораблей. Разработка ряда проектов по распоряжению Сталина была начата заново, с учетом опыта войны и новых воззрений на роль различных классов кораблей. Учитывая возросшую роль авианосцев, особенно в сражениях на Тихом океане, Сталин распорядился обратить внимание и на корабли этого класса. В том же году нарком ВМФ поручил ЦКБ-17 начать проработку первого советского авианосца (проект 72).
Несмотря на тяжелейшую ситуацию в промышленности, программа военного судостроения продолжала выполняться на всем протяжении войны. Разумеется, речь не шла о постройке Большого флота, задача была куда более скромной — восполнять боевые потери. И это, несмотря на все трудности, в целом удалось. В 1942–1944 годах ВМФ СССР получил от отечественных судостроителей 2 легких крейсера, 6 эсминцев и сторожевых кораблей, 29 подводных лодок, свыше 450 боевых катеров, около 300 различных тральщиков, свыше 1100 вспомогательных судов и различных плавучих средств.
Помимо восполнения корабельного состава, Кузнецов обсуждал со Сталиным и вопросы послевоенного базирования ВМФ СССР, практически всегда находя понимание. Так, на Тегеранской конференции 1 декабря 1943 года Сталин открыто заявил Черчиллю и Рузвельту, что Советский Союз не имеет незамерзающих портов на Балтийском море. Поэтому ему после войны будут нужны незамерзающие порты Кенигсберг и Мемель и соответствующая часть территории Восточной Пруссии, тем более что исторически — это исконно славянские земли. Скрепя сердце союзники согласились. Там же, в Тегеране, Черчилль и Рузвельт согласились с предложением Сталина о пересмотре некоторых положений конвенции Монтре, чтобы советский военно-морской флот получил право выхода в Средиземное море в любое время, независимо от желания турецких властей.
На всем протяжении Великой Отечественной нарком Кузнецов постоянно и последовательно вводил меры по моральному стимулированию военных моряков. Он учитывал как политическую и военную ситуации, так и общие приоритеты.
Первые четыре стрелковые дивизии «за боевые подвиги, за организованность, дисциплину и примерный порядок» 18 сентября 1941 года за героические бои под Ельней по решению Ставки Верховного Главнокомандования были переименованы в гвардейские. Так родилась советская гвардия. Практически сразу же после этого Кузнецов предложил Сталину ввести звания гвардейских для частей, соединений и кораблей в ВМФ.