В марте 1939 г. Н. Г. Кузнецов был назначен заместителем наркома, а через месяц с небольшим – народным комиссаром ВМФ СССР, главнокомандующим флотом. Сам Кузнецов свое столь стремительное восхождение по служебной лестнице объяснял впоследствии результатом чисток в армии и на флоте в 1937–1938 гг., когда Вооруженные силы СССР потеряли многих командиров и комиссаров самого высокого ранга. Действительно, его предшественники на этом посту, армейский комиссар I ранга П. А. Смирнов и командарм I ранга М. П. Фриновский, были репрессированы, так что принимать дела Кузнецову было не у кого. К тому же, не имея отношения к флоту по роду своей предыдущей деятельности, П. А. Смирнов и М. П. Фриновский не могли должным образом заниматься оперативно-стратегической подготовкой ВМФ, военно-морским искусством и т. п. Поэтому Кузнецов должен был столкнуться с большим количеством нерешенных проблем.
Прежде всего при создании Наркомата ВМФ в 1938 г. не было четко определено его место в структуре Вооруженных сил. Наркомат обороны и Генеральный штаб РККА занимались, по сути, только сухопутными войсками, а «флотские вопросы висели у них камнем на шее», – писал в воспоминаниях Н. Г. Кузнецов. Кроме того, каждый Наркомат «замыкался» на кого-то из членов правительства, за исключением НКО, НКИД и НКВД, и вновь созданного Наркомата ВМФ – ими Сталин руководил сам. «Это было и хорошо, и плохо, – вспоминал Кузнецов. – Хорошо потому, что многие важнейшие вопросы решались быстро и в самой высокой инстанции, а плохо из-за того, что никто иной, кроме Сталина (даже Молотов), их решать не хотел».
На подготовку к большой войне история отвела Кузнецову почти два года. Под его руководством были разработаны и обновлены боевые уставные документы, наставления и руководства, разработана система оперативных готовностей на случай войны.
Благодаря своевременным действиям Кузнецова, узнавшего накануне войны о подготовке высшим военным руководством страны тревожной директивы для приграничных округов, флот встретил 22 июня 1941 г. в состоянии боевой готовности № 1 и не понес в этот день серьезных потерь.
Летом 1941 г. Кузнецов выступил одним из инициаторов нанесения бомбовых ударов по Берлину силами морской авиации, базирующейся на Балтике. В августе – сентябре 1941 г. морские летчики совершили 52 самолетовылета и сбросили на Берлин 36 тонн фугасных бомб и 34 бомбы с листовками. Хотя материальный урон столице Третьего рейха оказался не слишком велик, политическое и морально-психологическое значение этих бомбардировок вполне очевидно.