Константин Иванович Душенов родился 28 июля 1895 года в многодетной крестьянской семье в деревне Ивановское (ныне Константиновка) Вологодской губернии. Окончив церковно-приходскую школу, юноша устроился разносчиком лекарств в одну из аптек Вологды. Как и многих из северян его призвали служить во флот. Февральскую революцию военмор Душенов встретил на крейсере «Аврора», а в марте 1917 года он уже был избран секретарем судового комитета. По приказу Военно-революционного комитета он организовал охрану Зимнего дворца, и благодаря его бдительности и решительности бесценные сокровища Эрмитажа не были разграблены. В Гражданскую войну он занимал должность командира порта на Волге — в Саратове, а затем в Астрахани, потом служил на Черноморском флоте. В 1923 году К. И. Душенов получил долгожданное направление на учебу в Военно-морскую академию, после успешного окончания которой служил начальником штаба соединения линейных кораблей Балтийского флота. В декабре 1929 года его, неожиданно для всех, назначили начальником Военно-морской академии. Как раз в это время в академии учился молодой флотский офицер Н. Г. Кузнецов. В 1931 году флагман флота 2-го ранга К. И. Душенов получил назначение на Черноморский флот начальником штаба Морских сил Черного моря. И вновь на короткое время пересеклись морские дороги земляков.
В декабре 1934 года К. И. Душенов прибыл в город Полярный на должность командующего Северной военной флотилией. 11 мая 1937 года флотилия была преобразована в Северный флот. Но недолго командовал флагман флота 1-го ранга К. И. Душенов Северным флотом. 22 мая 1938 года он был арестован и необоснованно репрессирован.
Н. Г. Кузнецов вместе со своим сокурсником В. А. Алафузовым дополнительно продолжили углубленно изучать французский и немецкий языки. К ним прикрепили двух опытных преподавателей: В. П. Саломон по немецкому и Гобар — по французскому языку.
Знание языков впоследствии очень пригодилось Н. Г. Кузнецову. Когда он получил назначение в Испанию, владение французским позволяло свободно вести переговоры, так как многие офицеры испанского флота знали этот язык. Вскоре Н. Г. Кузнецов освоил и испанский язык в такой степени, что мог обходиться без переводчика.
За время учебы в академии Николай Кузнецов совершил небольшое заграничное плавание на товарно-пассажирском пароходе «Кооперация» с заходом в Гамбург (Германия), Гуль и Лондон (Англия). Это была ознакомительная практика, в которой слушатели могли принять участие во время отпуска. Таких желающих оказалось двое: Н. Г. Кузнецов и Н. И. Зуйков. Академия предоставила им каюту, обеспечила бесплатным питанием и выделила немного валюты «на карманные расходы». Слушатели не были обременены никакими обязанностями, а во время стоянки судна в портах имели возможность посещать музеи, знакомиться с местными достопримечательностями и просто побродить по городу.
Капитаном «Кооперации» был опытный моряк В. В. Фролов, с которым позднее Н. Г. Кузнецова свела судьба во Владивостоке. В 1937–1938 годах капитан Фролов возглавлял пароходство, а Кузнецов командовал Тихоокеанским флотом.
Во время перехода слушатели перезнакомились со всей командой судна, часто бывали на мостике и в машинном отделении.
В Кильской бухте любознательный Кузнецов обратил внимание на небольшое соединение военных тральщиков, свидетельствующее о возрождении немецкого флота, пока — в рамках Версальского договора.
После Кильского канала судно взяло курс на Гуль — северный порт Англии. Слушатели увидели большую флотилию рыболовецких судов, занятых ловлей знаменитой шотландской сельди. Дальше путь лежал к столице Англии. Экскурсию по Лондону организовало советское торговое представительство. «Деловой город, — отметил Н. Г. Кузнецов, — во всем чувствуется давно установившийся порядок, который сохраняется не годами, а сотнями лет, — это хорошо, но скучно». После чопорного Лондона Гамбург показался настоящим портовым городом «немецкого стиля»: шумный и разгульный, не прекращающий жить ни днем ни ночью.
Плавание заняло около двух недель и принесло много пользы будущим командирам Красного флота.
В мае 1932 года состоялся выпуск слушателей Военно-морской академии. Наш герой окончил учебное заведение с отличием и с правом выбора моря. Он был награжден пистолетом системы Коровина с дарственной надписью в духе того времени: «Командиру-ударнику Н. Г. Кузнецову за успешное окончание военно-морской академии от Наркомморсил РККА. 4.5.1932». В музее академии до сих пор хранится этот уникальный пистолет-экспонат. Н. Г. Кузнецов, не стремившийся к высоким должностям, попросил направить его на один из крейсеров Черноморского флота в качестве старшего помощника командира.
В своих мемуарах он так объяснял это решение: «Я уже говорил, как важно любому офицеру пройти флотскую школу в должности старпома. Пожалуй, никто так не врастает в повседневную жизнь корабля, не чувствует ее пульса, как старший помощник».