В августе 1941 года стало ясно, что Таллин придется оставить, а корабли и войска вывести. Тогда Кузнецов обратился непосредственно в Ставку и получил разрешение на эвакуацию. Эвакуация флота и войск проходила организованно. Около 200 судов и транспортов, взяв на борт 23 тысячи солдат, совершили прорыв из Таллина в Кронштадт в неимоверно трудных условиях, через минные поля при постоянных атаках противника. Все эти силы влились в ряды защитников Ленинграда. Боевое ядро Балтийского флота было сохранено.

Опыт, полученный при прорыве из Таллина, был впоследствии использован при эвакуации войск из Одессы и Севастополя. Операция в Одессе была спланирована так умело, что флот не имел никаких потерь при ее проведении.

В начале 1942 года Кузнецов получил приказ о сформировании новых полков и бригад из моряков для сухопутных операций. В то же самое время шло формирование новой Волжской флотилии. До этого моряки героически защищали Москву, Одессу и Севастополь. В состав Волжской флотилии вошли моряки с Северного, Балтийского и Черноморского флотов, а новые части были укомплектованы в основном моряками Тихоокеанского флота и Амурской флотилии. Пока шло формирование, укомплектование и развертывание новых частей, прошло несколько месяцев. Затем они были переброшены на самый опасный участок фронта – Сталинград. Моряки вошли в состав 2-й гвардейской армии под командованием Р.Я.Малиновского, которая отбила все попытки немецких войск под командованием Манштейна деблокировать окруженную под Сталинградом 6-ю немецкую армию фельдмаршала Паулюса.

Еще одной сложной и ответственной задачей, которой пришлось заниматься Кузнецову в годы войны, стала организация морских перевозок из США в СССР. Путь был выбран самый короткий, но и самый трудный – через Северную Атлантику в Баренцево море и далее в порты Мурманска и Архангельска. Был разработан порядок встреч и сопровождения конвоев и меры по защите с моря и воздуха мест выгрузки. Для этих целей Северный флот был усилен подводными лодками с Тихого океана и сумел обеспечить проводку 77 конвоев (1464 транспорта) в порты СССР и из советских портов в порты союзников.

За годы войны флот вел непрерывные активные действия на коммуникациях противника. Одним из первых мероприятий флотов в начале войны стали минные постановки на путях возможного движения кораблей и судов противника. Всего было выставлено 9218 мин и минных защитников, на которых подорвалось около 110 транспортов и 100 кораблей охранения.

В декабре 1943 года Кузнецов доложил Верховному главнокомандованию свои соображения по поводу совершенствования практики оперативного руководства флотами со стороны командующих фронтами. В результате 31 марта 1944 года вышла директива Ставки ВГК, в которой формулировались основные принципы управления силами флота и их взаимодействия с другими видами вооруженных сил. Все флоты и флотилии во всех отношениях подчинялись наркому ВМФ. На отдельных этапах войны они могли быть переданы в оперативное подчинение командующих фронтами, округами, армиями, которые могли ставить им задачи, утвержденные Ставкой ВГК. Не связанные непосредственно с фронтами задачи, решаемые только Военно-Морскими Силами, должны ставиться флотам и флотилиям лично наркомом ВМФ. В соответствии с директивой Ставки ВГК нарком ВМФ стал именоваться главнокомандующим Военно-Морскими Силами СССР. На Н.Г.Кузнецова и ГМШ возлагалась обязанность самостоятельно разрабатывать крупные операции, согласовывать их с Генштабом или с командующими фронтами и нести полную ответственность за их проведение.