Следующим направлением, которое привлекло внимание наркома ВМФ, стал Новороссийск. Все лето продолжалась подготовка наступления на Северном Кавказе. Во второй половине августа сначала заместитель начальника Генерального штаба А.И. Антонов ознакомил Кузнецова с предстоящей операцией. Затем Сталин вызвал моряка и, выслушав наметки плана освобождения Новороссийска, направил на юг, чтобы оценить положение на месте. 18 августа 1943 года Николай Герасимович вылетел в Краснодар, где командующий Северо-Кавказским фронтом И.Е. Петров ознакомил его с планом разгрома таманской группировки противника. В первую очередь предстояло взять Новороссийск атаками с Малой Земли и с востока. Петров намечал десант у Анапы, однако согласился с предложением моряков провести высадку прямо в Новороссийский порт, где десант могла поддержать береговая артиллерия.
С трудом Н.Г. Кузнецов добрался по разбитым дорогам до Геленджика, где располагался командный пункт флота. Там уже усиленно разрабатывали план операции. Благодаря тщательной разведке и подготовке высадка десанта в Новороссийске в ночь на 10 сентября 1943 года прошла успешно. После ударов с воздуха и артиллерийского обстрела первая группа из 9 торпедных катеров атаковала торпедами огневые точки на молах; высаженные штурмовые группы подорвали боносетевые заграждения. Через открытый проход в порт ворвалась вторая группа из 13 торпедных катеров, которые атаковали вражеские объекты на берегу. Третья группа катеров выпустила торпеды по причалам. После такой подготовки в порт вошли катера, которые высадили на берег около 4 тысяч человек. Так как наступавшим группировкам 18-й армии не удалось прорвать позиции противника, в ночь на 11 сентября в порт высадили подкрепления. Кузнецов дал разрешение, хотя и понимал, что операция будет стоить жертв. Несмотря на значительные потери, усиленный десант помог восточной группировке прорвать вражескую оборону. Германские войска под угрозой окружения начали отходить. 16 сентября Новороссийск был освобожден.
Освобождение Новороссийска открыло возможность развития операций в сторону Крыма. Еще в конце января 1943 года Н.Г. Кузнецов предложил воссоздать Азовскую флотилию, ибо северная часть Азовского моря была освобождена, а войска, наступавшие к Перекопу и Таманскому полуострову, нуждались в поддержке с моря. Базой флотилии, возглавлял которую вновь С.Г. Горшков, стал Ейск. В распоряжение флотилии возвратили корабли и катера, уведенные на Черное море. К лету флотилия обрела силу и отбивала нападения германской авиации. В августе-сентябре 1943 года суда флотилии высадили несколько десантов, способствуя освобождению Таганрога, Осипенко и других прибрежных пунктов. После взятия Новороссийска открылась возможность овладеть всем Таманским полуостровом как плацдармом для вторжения в Крым.
Таманский полуостров противник сильно укрепил. Доставку грузов через Керченский пролив обеспечивали значительные германские морские силы, минные заграждения и береговая артиллерия. Тем не менее Черноморский флот десантом 20 сентября 1943 года занял Анапу. Последующие десанты, высаженные Азовской флотилией и Черноморским флотом в разных пунктах Тамани, способствовали наступлению войск Северо-Кавказского фронта. В октябре весь Таманский полуостров был освобожден[96].
Северный флот, как и ранее, в 1943 году главным образом обеспечивал переходы конвоев и оставался в непосредственном подчинении наркома ВМФ. В этом году германский флот использовал против судоходства на Севере преимущественно подводные лодки, так как значительную часть бомбардировочной авиации пришлось перебросить на другие участки фронта. В январе и феврале три союзных конвоя достигли советских портов без потерь. Однако с началом полярного дня союзники прекратили отправку конвоев и возобновили доставку грузов северным маршрутом только в ноябре 1943 года. Так как в Альтен-фьорде базировались германские линейные корабли, для прикрытия конвоев англичане посылали линкоры и крейсера. В декабре 1943 года Н.Г. Кузнецов по указанию Ставки побывал в Полярном. Именно в эти дни, 26 декабря, когда линкор «Шарнхорст» попытался атаковать конвой РА-55А, шедший из советских портов, он в свою очередь оказался под обстрелом кораблей прикрытия конвоя и был потоплен.
Нарком ВМФ побывал на полуострове Средний, где располагался командный пункт командующего Северным оборонительным районом. Оттуда можно было просматривать весь Варангер-фьорд, через который проходил маршрут неприятельских перевозок. Кузнецов сам наблюдал один из боев с неприятельским конвоем, прикрытым дымовой завесой. По судам вели огонь советские береговые батареи, им отвечали германские. Так как эффективность стрельбы по площадям оказалась невысока, вслед за тем конвой атаковали торпедные катера, для которых неприятельская дымовая завеса служила укрытием. Кузнецов отмечал в воспоминаниях, что в 1943 году на Севере основные потери противнику нанесли авиация, подводные лодки и торпедные катера.