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