Успешные действия моряков и рост числа награждений вызвал к жизни проект учреждения специально морских наград. В середине 1943 года нарком ВМФ сделал такое предложение Сталину, но не вызвал его энтузиазма. Тем не менее Кузнецов отдал указания проработать идею в Главном морском штабе. Речь шла об орденах Ушакова и Нахимова. Сразу же появился вопрос: какой орден считать старшим? Не все знали, каковы заслуги Ф.Ф. Ушакова, основательно забытые в народе с XVIII века. Такие же вопросы возникли и в правительстве. После обсуждения проекта правительственной комиссией 3 марта 1944 года вышел Указ Президиума Верховного Совета СССР об учреждении орденов Ушакова и Нахимова I и II степеней и медалей Ушакова и Нахимова. Свою роль сыграл И.В. Сталин, который рассмотрел представленные Кузнецовым проекты статутов и рисунки новых наград, без вопросов утвердил эскизы ордена Ушакова и медалей, но предложил украсить орден Нахимова рубинами. Николай Герасимович писал: "Возражать не было оснований. Так орден Нахимова I и II степеней получился, по-моему, самым красивым, но и дороговатым".
После публикации указа пошли письма. Люди больше знали Нахимова и не понимали, почему орден Ушакова имеет более высокий статус. В годы войны попробовали разъяснить заслуги Ф.Ф. Ушакова через газеты и радио. А после Победы сняли фильм "Адмирал Ушаков", который консультировал И.С. Исаков. Появление фильма на экранах сразу прекратило поток писем.
В 1944 году Николаю Герасимовичу удалось решить важнейший вопрос взаимодействия родов войск в операциях. В послевоенных воспоминаниях он писал: "Мы не имели единого взгляда на доктрину ведения войны… Доктрина, как нечто плохо осязаемое для нас, скрывалась в голове Сталина, а он неохотно делился своими мыслями и намерениями… И не случайно сейчас нельзя привести в пример ни одного документа за его подписью, в котором излагались бы взгляды на ведение войны, ее характер и взаимоотношения наркоматов". До войны считали, что Ставка Главнокомандования будет ставить задачи флотам на кампанию, а оперативные задачи в ходе кампании – нарком ВМФ и командующие объединениями, в подчинении которых окажутся флоты. Фактически, как известно, война пошла иначе, чем ее планировали. Общее руководство фронтами и подчиненными им флотами оказалось в руках Генерального штаба. Однако Генеральный штаб за два года войны ни разу не ориентировал Главный морской штаб по вопросам дальнейшего хода военных действий, что затрудняло постановку соответствующих задач флотам. Так как наладить обмен информацией между Генеральным и Главным морским штабами Кузнецову не удалось, он в декабре 1943 года доложил непосредственно Сталину, что командующие фронтами и армиями даже не ставят в известность подчиненные им морские силы о намеченных операциях. Нарком предложил, чтобы оперативные директивы флотам исходили только из Ставки Верховного Главнокомандования и чтобы Генеральный и Главный морской штабы объединили усилия при подготовке оперативных директив флотам и флотилиям. Для лучшего взаимодействия было предложено при штабах фронтов (армий) создать морские отделы, подчиненные соответствующим начальникам штабов. Сталин согласился. Но лишь 31 марта 1944 года вышла директива Ставки, в которой были сформулированы основные принципы управления силами флота и их взаимодействия с другими силами. Флоты и флотилии стали подчиняться наркому, как главнокомандующему ВМФ. 5 апреля Кузнецов подписал приказ о формировании морских отделов и морских групп. Вскоре начальники Генерального и Главного морского штабов утвердили положение о морских отделах. После этого проекты оперативных директив Верховного главнокомандующего для флотов разрабатывали в Главном морском штабе. Затем их согласовывали с начальником Генерального штаба. 8 июня было введено в действие Положение о морском представительстве при фронтах, отдельных армиях и военных округах Красной Армии, подготовленное Главным морским штабом по опыту первых наступательных операций 1944 года. Благодаря принятым мерам ВМФ сыграл значительную роль в проведении наступательных операций. Тем не менее лишь 2 февраля 1945 года Н.Г. Кузнецова ввели в состав Ставки Верховного Главнокомандования.
В 1944 году и на Северном флоте появилась эскадра. После капитуляции Италии в конце июля 1943 года союзники получили в качестве трофеев весь итальянский флот. Ставка потребовала от Кузнецова сведения о составе этого флота. На конференции министров иностранных дел СССР, Англии и США советская делегация предложила передать Советскому Союзу треть флота, то есть линкор, крейсер, 8 эсминцев и 4 подводные лодки. После длительных переговоров только 7 февраля 1944 года союзники обещали предоставить все эти корабли. Однако, чтобы не настроить против себя итальянцев, англичане и американцы на время войны выделили старые линейный корабль "Ройял Соверин", крейсер "Милуоки", 8 эсминцев и 4 подводные лодки из состава своих флотов. Доложив Сталину о том, что союзники предлагают старые корабли, Кузнецов предложил направить их на Северный флот для охранения конвоев, противолодочной борьбы и охраны побережья. Сталин согласился. Для приемки и доставки кораблей назначили вице-адмирала Г.И. Левченко, спешно собрали в Архангельске экипажи для кораблей. Ответственным за комплектование назначили Кузнецова, который срочно выехал на Север.
Глава английской военно-морской миссии высказал сомнение, что советские моряки смогут быстро освоить большие, незнакомые для них корабли. Чтобы упростить задачу, для линкора моряков набирали с линкоров, для крейсера – с крейсеров. Потребовалось собрать около 3 тысяч человек. 28 апреля они были отправлены с очередным конвоем. Н.Г. Кузнецов специально прилетел в Архангельск, чтобы проводить их. Команды благополучно достигли Англии. Правда, 30 апреля был потоплен транспорт, на котором располагалась команда одного из эсминцев, но всех спасли. В британских портах советские моряки решительно взялись за освоение неизвестной техники, несмотря на то что не знали языка. Линкор, названный "Архангельск", приняли за двадцать дней, и 30 мая над ним взвился Военно-морской флаг СССР. Успешно прошли как приемка других кораблей, так и их подготовка к переходу. Озадаченные англичане поговаривали, что вместо матросов прислали инженеров. А 17 августа линкор, крейсер и эсминцы вышли из Скапа-Флоу и 24 августа благополучно прибыли в Мурманск, где крейсер был назван "Мурманск". За кораблями, составившими эскадру, последовали 4 подводные лодки с индексом "В"; лишь В-1 не дошла до цели. Все полученные корабли советские моряки успешно использовали до конца войны, а в 1947 году их возвратили хозяевам в обмен на 33 итальянских корабля, переведенные на Черноморский флот.
Еще большую трудность составила доставка предоставленных американцами небольших охотников за подводными лодками и тральщиков. Так как на судах их разместить не удалось, советские моряки решили привести эти малопригодные для океанского плавания суденышки своим ходом. Специалисты Главного морского штаба вынесли заключение, что вряд ли катера и тральщики смогут пересечь океан. Наркому ВМФ пришлось немало подумать, прежде чем он подписал приказ о переходе судов. Первыми за двадцать суток цели достигли 12 охотников за подводными лодками (БО) и 12 тральщиков типа AM; они сразу же включались в боевую службу. Позднее на Северный флот своим ходом перешли еще 34 охотника и 24 тральщика. Советские моряки продемонстрировали как мужество и морское искусство, так и умение изучать в короткий срок сложную технику. Радисты осваивали радиолокаторы, артиллеристы – неизвестные им ранее автоматические пушки. В воспоминаниях Кузнецов отмечал, что благодаря пополнению флот мог выделять для охранения конвоев каждый раз до 40 кораблей и 2 авиационных дивизий.
Весной 1944 года Ставка стала больше внимания уделять действиям морских сил, которые принимали участие в освобождении берегов и приморских городов, а И.В. Сталин сказал Н.Г. Кузнецову: "Наступило время для более активных действий флотов в море".
На Черном море это означало в первую очередь освобождение Крыма и Одессы. Потеря трех эсминцев, неполадки при высадке десанта у Керчи и мнение Сталина, что Л.A. Владимирский и И.Е. Петров спорят между собой, вызвали решение сменить командование перед началом активных действий на Черном море. Петрова сняли после того, как Приморская армия была подготовлена им к наступлению. На командование Черноморским флотом вернули Ф.С. Октябрьского. Кузнецов вспоминал: "Ни Генштаб, ни Наркомат ВМФ не вносили предложений о смене командования Приморской армии и Черноморского флота. С.М. Штеменко пишет, что для него остается неразгаданной причина снятия И.Е. Петрова, а для меня до сих пор не ясна причина освобождения от должности Л.A. Владимирского".
По плану прежде вторжения в Крым следовало взять Одессу, которую противник собирался упорно оборонять. Чтобы блокировать неприятельские коммуникации, использовали подводные лодки, действовавшие из Поти, Очамчире и Туапсе. Часть торпедных катеров и морской авиации перебазировали в Каркинитский залив. На освобожденной Кинбурнской косе в Скадовске возобновили Очаковскую военно-морскую базу. Оттуда катера атаковали неприятельские суда в районе Одессы и Очакова, позднее у Ак-Мечети, Евпатории и берегов Румынии. Морская авиация бомбила Констанцу и Сулину, действовала против судов в море. При поддержке флота с 26 марта по 14 апреля войска 3-го Украинского фронта провели Одесскую наступательную операцию. Начал операцию небольшой десант лейтенанта К.Ф. Ольшанского, который высадился под Николаевом, вызвал тревогу и двое суток притягивал силы противника. А 28 марта войска фронта освободили Николаев. Моряки участвовали и во взятии Очакова, высадив 31 марта группу морских пехотинцев у Очаковского маяка. Пока десантники отвлекали противника, войска овладели Очаковом в тот же день. Утром 10 апреля ударами с трех сторон была освобождена Одесса.
Еще не пришла к концу операция под Одессой, а уже 11 апреля Ставка утвердила директиву на освобождение Крыма, подготовленную Главным морским штабом. Замысел операции заключался в одновременном наступлении на Симферополь и Севастополь со стороны Перекопа и с Керченского полуострова. Черноморский флот и Азовская флотилия должны были содействовать наступлению Отдельной Приморской армии на первом этапе борьбы и всему фронту – на последнем. В период решительного наступления морякам следовало блокировать с моря крымские порты и коммуникации противника, а также готовиться к перебазированию в Севастополь и созданию Дунайской флотилии.
Когда Кузнецов участвовал в рассмотрении директивы И.В. Сталиным, Верховный главнокомандующий дал прямое указание не рисковать крупными кораблями. Основная тяжесть действий легла на авиацию, легкие силы и подводные лодки.
Приказ наркома ВМФ предписал бригаде подводных лодок: "Во взаимодействии с авиацией уничтожать транспорты и плавсредства противника на коммуникациях в северо-западной части Черного моря". Несмотря на действия неприятельской авиации, подводники выходили к берегам Румынии, Болгарии и Крымского полуострова, топили неприятельские суда. Ночами из засад активно действовали торпедные катера, которым часто помогали самолеты-разведчики. Некоторые катера были вооружены реактивными установками. Морякам с торпедных катеров также удалось потопить несколько судов и кораблей. Особенно крупные потери противник понес при эвакуации Крыма.
Наступление 4-го Украинского фронта под Перекопом началось утром 8 апреля 1944 года после двух с половиной часов обработки неприятельских позиций на перешейке и у Сиваша обстрелом артиллерии и ударами с воздуха. В наступление перешла и Отдельная Приморская армия. К 13 апреля, сокрушив сопротивление противника, советские войска вышли к внешним обводам обороны Севастополя. Штурм начали 5 мая, а 9 мая город был освобожден. Большую часть войск противника в Крыму удалось уничтожить или пленить.
После тщательного обследования бухт и траления днем 5 ноября 1944 года эскадра Черноморского флота вступила в Севастополь, отметив возвращение в главную базу двадцать одним залпом из ста орудий. В начале февраля 1945 года нарком ВМФ побывал в Севастополе и видел линкор, крейсера, эсминцы, стоявшие на своих местах.
6 июня 1944 года союзники наконец высадили войска в Нормандии. Появился долгожданный второй фронт. Однако накал боевых действий на советско-германском фронте не ослабевал, ибо боевые действия во Франции мало оттягивали сил на запад. По-прежнему германские корабли и самолеты угрожали конвоям, продолжавшим идти из Исландии в Мурманск и Архангельск. Если на Черном море ввиду освобождения советских берегов стоял вопрос о переносе боевых действий к берегам Болгарии, Румынии и на Дунай, то на Севере противник оставался под Мурманском, а на Балтийском море германские перевозки продолжали играть большую роль для хода войны. На всех флотах оставались постоянные задачи (траление, обеспечение своих перевозок и борьба с перевозками противника). Поэтому для моряков существовало широкое поле деятельности.
Следующим этапом общего наступления стали действия на берегах Балтики. После деблокирования Ленинграда в марте 1944 года фронты перешли к обороне. Требовалось время для подготовки к последующему наступлению. В частности, чтобы придать Краснознаменному Балтийскому флоту боеспособность, потребовалось вернуть на корабли хотя бы часть специалистов, которые служили в сухопутных частях. Уже в начале марта И.В. Сталин в разговоре с Кузнецовым выяснил, каковы возможности морских сил на Балтике, и утверждал, что наступает период более активных действий на море. По вызову Верховного главнокомандующего для более обстоятельного выяснения положения дел на театре в Москву прибыл В.Ф. Трибуц. Сталин внимательно выслушал Трибуца, который заверил, что к вскрытию льдов флот будет готов выйти в море. Сталин сказал, что у моряков появляется возможность проявить себя на море, и поставил основные задачи: вести борьбу на коммуникациях противника, защищать свои морские сообщения и охранять занятое побережье. Сталин одобрил мысли Кузнецова и Трибуца о том, что следует действовать на море преимущественно авиацией, а там, где возможно, использовать и надводные корабли. Он обратил особое внимание на необходимость борьбы с минной опасностью и предупредил, что вскоре потребуется поддержка флота со стороны моря. В отличие от прежней практики, когда флоты при проведении операций оперативно подчиняли сухопутным войскам, Сталин дал указание: "Задачи по боевым действиям на море будут ставиться главнокомандующим Военно-Морским Флотом", подразумевая Николая Герасимовича. Однако только с начала февраля 1945 года по инициативе Кузнецова была опубликована директива, которая узаконила роль наркома ВМФ как главнокомандующего флотом.
Флот приступил к подготовке Выборгской операции. Н.Г. Кузнецову дважды пришлось побывать в Ленинграде и организовать координацию действий морских сил с войсками Ленинградского фронта. По замыслу операции 21-й и 23-й армиям при поддержке авиации и флота следовало прорвать долговременную оборону противника на Карельском перешейке в направлении Выборга. До начала операции Краснознаменному Балтийскому флоту предстояло с 23 мая по 8 июня перевезти на Лисий Нос 21-ю армию. Прорыв следовало начать с обстрела морской артиллерии и атак авиации на мощный опорный пункт противника Старый Белоостров. В ходе наступления флоту и Ладожской флотилии предстояло огнем поддерживать войска, прикрывать с моря их фланги, уничтожать боевые корабли и транспорты противника.
Операция прошла успешно. 21-ю армию моряки перевезли незаметно. После длительного обстрела артиллерии, которая разрушила большинство укреплений противника, армия двинулась вперед и 11 июня вышла к новой линии Маннергейма. Вновь морская артиллерия расчистила путь наступающим войскам. Морская авиация и торпедные катера, господствовавшие в Выборгском заливе, не позволили неприятельским кораблям оказать поддержку своим силам, тральщики прокладывали фарватеры. 20 июня советские войска взяли Выборг.
Военный совет Ленинградского фронта поручил флоту своими силами занять острова Бьёркского архипелага, без чего нельзя было продолжать наступление. Уже 21 июня моряки высадили десант на остров Пийсари и на следующий день овладели им. Затем были заняты Торсари, Бьёркё и другие острова. Сложнее оказалось взять остров Тейкарсари, на который германское командование перебросило дивизию в помощь финнам. Первая попытка высадки в ночь на 1 июля не удалась. Однако в ночь на 4 июля высаженная с кораблей КБФ 224-я дивизия овладела Тейкарсари и Суонинсари. Авиация флота успешно истребляла неприятельские корабли и суда. В результате совместных действий армии и флота Выборгский залив и его северное побережье были очищены от неприятеля.