Благорасположение вождя подкреплялось его ближайшим окружением. В июле 1939 года Кузнецов вместе с куратором ВМФ от ЦК ВКП(б) Ждановым отправился в Ленинград. На верфях ознакомился с ходом строительства новых кораблей, затем занялся военно-морскими училищами, которым после расширения уже не хватало старых помещений. Найти новые в центре Ленинграда было непросто, помог авторитет Жданова. Кузнецов добился также передачи здания Фондовой биржи на Васильевском острове военно-морскому музею.
Затем оба посетили Кронштадт, где Жданов выразил желание посмотреть учения Балтийского флота. Вместе с Галлером и командующим эскадрой Несвицким они вышли в море на линкоре «Октябрьская революция». В недолгом походе обсуждали перенесение главной базы Балтийского флота ближе к устью Финского залива — в Таллин. После подписания договора с Эстонией о размещении на ее территории частей РККА и ВМФ СССР базирование Балтийского флота значительно расширилось, а пребывание штаба флота в Кронштадте усложняло управление. Жданов с мнением моряков согласился и обещал поддержать Кузнецова. Позже, в мае 1940 года, Сталин его предложение принял.
Оценку учений Кузнецов дал на обсуждении в Доме флота. Отметил немало недостатков и вновь обратил внимание на доктрину «первого залпа». Она подразумевала упреждение противника в артиллерийской дуэли, причем на уровне не только отдельных кораблей, но и соединений. С тех пор борьба за «первый залп» не сходила с повестки дня всех флотов. Так началось введение знаменитой «кузнецовской» системы боеготовности.
Первые шаги нового наркома продемонстрировали, что он хорошо представляет круг первостепенных задач и серьезно взялся за их решение. В числе важных его достижений следует отметить тот факт, что ему удалось отстоять подчинение морской авиации флоту. Начальником управления назначили генерал-лейтенанта С. Жаворонкова, с которым Кузнецов служил на Черноморском и Тихоокеанском флотах.
Вскоре после своего назначения наркомом ВМФ Кузнецов женился. Избранницей его стала молодая девушка-москвичка Вера Николаевна Шитохина, которая будет ему верным другом до конца жизни. В 1940 году у них родился первенец Николай.
После своего образования Наркомат ВМФ занял особое положение. Если остальные наркоматы, за исключением НКО, НКИД и НКВД, замыкались на одного из заместителей предсовнаркома, то этот подчинялся непосредственно Сталину. Это было и хорошо и плохо. Хорошо, потому что некоторые важные вопросы решались быстро в самой высшей инстанции, а плохо потому, что никто, кроме Сталина, даже Молотов, решать их не мог. При этом вопрос создания Большого флота, которым Сталин много занимался до осени 1939 года, был отложен до лучших времен.
Первое время после назначения наркомом Сталин относился к Кузнецову с особой заботой — учил, поддерживал, объяснял и поправлял, помогал «встать на крыло». Кузнецов же был в это время предельно послушен и беспрекословно исполнителен. Впоследствии этот период он назовет «медовым месяцем» их отношений. Спустя некоторое время Сталин, посчитав, что молодой нарком уже освоился с делами, перестал его опекать и стал относиться так же, как и ко всем другим наркомам, — предельно требовательно, взыскующе и сурово.
Перемена в отношении Сталина Кузнецова задела. Видимо, он полагал, что особое отношение вождя к нему сохранится навсегда. Поэтому в ответ молодой нарком порой фрондировал, излишне категорично отстаивая свою позицию по вопросам, в которых считал себя правым. Иногда это ему удавалось, иногда нет. Прямой (и даже дерзкий) характер Кузнецова Сталину импонировал, но когда тот переходил границы, вождь его осаживал, порой весьма резко.
Разумеется, Кузнецов знал, чего хотел. Уже с начала работы в Москве его, как моряка-профессионала, озадачивали некоторые сталинские решения. Так, выслушав доклад, в котором Кузнецов доказывал большое значение зенитного вооружения для современных кораблей, Сталин заявил, что «драться возле Америки мы не собираемся», и отверг его предложения по усилению ПВО кораблей.
