Позднее Н. Г. Кузнецов на собственном командирском опыте не раз убеждался в том, что культура, воспитание и знание техники неразделимы. Подбор кадров на корабли из наиболее образованной, культурной и развитой молодежи обеспечивал высокий уровень боевой и политической подготовки личного состава как в мирное, так и в военное время.

Короткие встречи с М. В. Фрунзе и очень кратковременная служба под его руководством оставили у будущего советского флотоводца впечатление о наркомвоенморе как о военном и политическом руководителе незаурядного таланта и очень высокой культуры.

В октябре 1926 года Николай Кузнецов простился с училищем. Многие выпускники мечтали служить на линкоре «Парижская коммуна», самом крупном военном корабле, на котором они проходили практику. Отличники имели право по своему желанию выбирать место предстоящей службы. Курсанта Кузнецова влекло неведомое: он избрал службу на новом крейсере «Червона Украина» («Адмирал Нахимов») Черноморского флота.

Служба на первенце советского судостроения крейсере «Червона Украина» оказалась нелегкой. Самая современная, а значит, еще неосвоенная техника, недостаточно подготовленный личный состав корабля, слабая поначалу дисциплина — все это создавало немалые трудности для молодого флотского офицера. Молодой вахтенный начальник крейсера настойчиво постигал боевую технику, корабельную организацию, тактику применения морского оружия. Постепенно набирался опыта, как надо обучать и воспитывать подчиненных, строить с ними взаимоотношения. Н. Г. Кузнецов убедился, что подразделение только тогда способно выполнять поставленные задачи, когда ведется повседневная, кропотливая организаторская работа, без окриков, без понуканий, без подавления воли и инициативы подчиненных. Такого стиля флотской службы молодой офицер придерживался и в будущей своей деятельности.

Но ему повезло с наставниками. Почти половиной личного состава корабля командовал старший инженер-механик Василий Артемьевич Горшков — опытный моряк, долго плававший на торговых судах. Он был командирован на «Червону Украину», когда крейсер еще достраивался, и вместе с заводскими инженерами участвовал в монтаже механизмов. В. А. Горшков был уже не молод, ему перевалило за сорок лет. Много вложил труда этот скромный механик, чтобы крейсер стал самым быстроходным кораблем Черноморского флота. Особенно внимательно, с трогательной заботой он относился к молодым командирам, помогая и делом, и словом. Большую роль В. А. Горшков сыграл и в жизни будущего Адмирала Флота Советского Союза.

Командир крейсера Н. Н. Несвицкий часто напоминал молодому офицеру Кузнецову: «Корабль — это твой дом». И это на самом деле так. Позднее адмирал Н. Г. Кузнецов оставил нежные строчки о своем «морском доме»: «Любовь к кораблю — дело естественное. Она основана не на качествах корабля, сколько на привычке к любому кораблю, где человек долго служил, вложил в него много сил и энергии. „Привычка свыше нам дана“ и действительно составляет счастье тех, кто серьезно относится к службе. Мне думается, командир вспомогательного судна или малого тральщика гордится им, не считает себя хуже командира более крупного корабля и самой современной подводной лодки. И он прав. Не место красит человека…» Позднее молодым командирам флота адмирал Н. Г. Кузнецов приводил свой любимый афоризм: «Единственно стоящее дело для моряка — командовать кораблем!»

На Архангельском Севере поморы с детства были обучены ходить на веслах и «под паруском» по Северной Двине и студеному «Гандвику-морю». Первые навыки владения парусом и веслом юноша Кузнецов получил у города на Белом море. Он на всю жизнь полюбил парусное дело и часто уже курсантом военно-морского училища ходил на шлюпке под парусами. Эти навыки пригодились и на Черном море. На крейсере «Червона Украина» молодой морской офицер был назначен старшим вахтенным начальником корабля и на этой должности он в полной мере раскрыл свои достоинства. Обучая краснофлотцев гребле и хождению под парусом, все стали замечать, что «кузнецовская» шлюпка всегда обгоняла шлюпки других рот, как под веслами, так и под парусом. Среди командиров в кают-компании заговорили о северянине как о молодом, но дельном моряке, любящем морское дело, море, корабль. У сослуживцев в последующем сложилось общее мнение, что Николай Герасимович прост с людьми, бесхитростен, правдив. Всегда был готов, в большом и малом, помочь и помогал своим товарищам. Он не умел и не пытался хоть как-нибудь подхалимничать перед начальством или заискивать перед подчиненными. Больше того, он не боялся возражать начальству, если чувствовал себя правым. Ветераны крейсера позднее вспоминают такой случай. Во время учений, на которых присутствовал командующий Черноморским флотом флагман 2-го ранга В. М. Орлов, крейсер «Червона Украина» должен был развить полный ход. Корабль дрожал всем своим корпусом, а стрелка указателя скорости остановилась на цифре 30. Комфлота обратился к командиру дивизиона: «Товарищ Шельтинга, это что — предел скорости?» Не подумав, тот сразу ответил флотоводцу: «Так точно». Рядом на мостике стоял вахтенный начальник. «Товарищ Кузнецов, — обратился к нему Орлов, — а вы, помнится, на партсобрании говорили, что дали 31 узел, ведь один узел в бою может сыграть решающую роль. Комдив забыл или я не понял его?» Николай Герасимович, не смутившись, четко ответил комфлоту: «Так точно, командир дивизиона, видимо, ошибся, крейсер может дать 31 узел». Через несколько минут стрелка прибора полезла на 31-й узел. Кузнецов не побоялся испортить отношения с комдивом и доложил правдиво. Эта прямота суждений была основной чертой его характера и, к сожалению, в дальнейшем часто портила его отношения с высоким начальством, не желавшим вникнуть в существо флотского дела.

Старшим вахтенным начальником на крейсере служил Л. А. Владимирский, которого аттестовали на флоте так: «Лучшего помощника не может быть». Он окончил военно-морское училище на год раньше Кузнецова. В годы Великой Отечественной войны он высаживал десанты возле Одессы, участвовал в прорыве блокады Севастополя. Командовал соединениями боевых кораблей на Черноморском флоте и Балтике. В дальнейшем адмирал флота, заместитель главкома ВМС по кораблестроению.

Служба на черноморском крейсере свела Н. Г. Кузнецова с молодым штурманом Ю. А. Пантелеевым, с которым на протяжении всей последующей флотской жизни его связывали добрые и дружеские отношения.

О Юрии Александровиче Пантелееве стоит рассказать подробнее. В молодые годы судьба закинула его в дальний северный порт Архангельск. 9 мая 1924 года Совет труда и обороны (СТО), в связи с необходимостью усилить охрану советского побережья Японского и Охотского морей, где орудовали японские промысловые суда, хищнически истреблявшие пушного и морского зверя, ценные породы рыб, принял решение направить из Архангельска на Дальний Восток посыльное судно «Боровский».

Командиром корабля был назначен А. С. Максимов, в прошлом царский вице-адмирал, комиссаром — П. И. Смирнов, активный участник Гражданской войны. Подготовка к ответственному переходу началась с формирования команды.

Ее костяк составили комсомольцы-военморы, призванные во флот в 1922 году по решению V Всероссийского съезда РКСМ. В состав экипажа были включены выпускники штурманского класса Высших специальных курсов командного состава Военно-морского флота СССР. Наставниками молодых штурманов стали преподаватели военно-морского училища Н. А. Сакеллари и Н. Ф. Рыбаков. Из числа этих слушателей, участников похода на «Воровском», вышли впоследствии видные советские флотоводцы — И. С. Юмашев, Н. Ф. Заяц и Ю. А. Пантелеев. 12 июля 1924 года комсомольцы и трудящиеся Архангельска тепло проводили военморов «Воровского» в ответственный поход. Это был первый советский корабль, совершивший дальнее плавание из Архангельска во Владивосток по четырем океанам. 20 ноября 1924 года «Боровский» отдал якорь в бухте Золотой Рог. За его кормой осталось 13 927 миль. Для слушателей высших штурманских классов это была прекрасная практика.