Из воспоминаний однокашника Кузнецова Е. А. Чернощека:
«В 1926 году мы окончили Военно-морское училище. По успеваемости Николай Герасимович и я оказались в первом десятке, и нам в порядке поощрения было предоставлено право выбрать море и корабль. Он выбрал Черное море и крейсер „Червона Украина“, а я Балтийское море и линкор „Октябрьская Революция“. В октябре 1926 года мы разъехались по своим морям и на свои корабли»[4].
Сам Кузнецов вспоминал о своем выборе места службы так: «В последний день пребывания в училище мы собрались в нашем кубрике… Ожидали начальника курса В. И. Григорьева, который должен был зачитать приказ о распределении. В тот год курсанты, отлично окончившие училище, получили право сами выбирать место службы. Когда среди отличников назвали мое имя, я встал и, вытянувшись, доложил: „Желаю служить на Черном море“.
— Куда ты, северный медведь? — тихонько потянул меня за руку сидевший рядом товарищ. — Ты там от жары ноги протянешь…
Но судьба моя была уже решена. В списке против моей фамилии стояло: Черноморский флот. Можно только гадать, как сложилась бы у меня служба, не откажись я от назначения на балтийские линкоры…»
Приказом по РККФ № 579 от 12 октября Н. Г. Кузнецов был назначен в Морские силы Черного моря и направлен в распоряжение начальника штаба МСЧМ. Вместе с ним туда отправились Л. А. Владимирский, Н. Г. Александров, Ф. С. Маглич, И. А. Рублевский, Е. Е. Полтавский и другие выпускники.
Кузнецов поездом прибыл из Ленинграда в Севастополь и сразу отправился в штаб флота. Никаких вопросов у кадровиков к молодому командиру не возникло, и 27 октября Кузнецов был назначен вахтенным начальником крейсера «Червона Украина». При этом по традиции кроме основной должности ему были вменены обязанности командира первого плутонга (батареи) и командира строевой роты. К этому времени крейсер еще только достраивался в Николаеве. Поэтому молодого выпускника отправили прямиком на судостроительный завод. Спустя полгода крейсер был принят в боевой состав РККФ.
Заложенный в 1913 году в Николаеве как легкий крейсер типа «Светлана», он и для середины 20-х годов оставался вполне современным. Для малочисленных Морских сил Черного моря ввод его в строй стал событием огромной важности.
К моменту прибытия Кузнецова командиром крейсера служил легендарный Н. Н. Несвицкий — бывший мичман императорского флота, принявший в 1917 году Советскую власть и командовавший всю Гражданскую войну эсминцем «Азард». Именно благодаря его профессионализму и мужеству «Азард» оказался единственным уцелевшим кораблем из отряда эсминцев, попавших в 1919 года на английское минное поле. В том же году «Азард» одним выстрелом уничтожил английскую подводную лодку L-55. У его командира было чему поучиться.
Некоторые из сослуживцев Кузнецова по «Червоной Украине» впоследствии войдут в так называемую знаменитую «команду Кузнецова», когда тот возглавит ВМФ. Среди них будут его однокашники Вдовиченко, Владимирский, старший штурман Ю. А. Пантелеев. Да и самому Несвицкому Кузнецов также попытается в будущем помочь, назначив его на вице-адмиральскую должность, но… Несвицкий не доедет до нового места службы. Н. Г. Кузнецов так вспоминал о первых шагах на крейсере:
