«Однако сухопутный образ жизни был не для него. При первой же возможности, которая представилась в 1920 году, он подал заявление о поступлении на новый военно-морской немецкий флот, который только начал возрождаться. Он был твердо намерен осуществить свою детскую мечту и стать моряком».
Вплоть до середины 30-х годов, когда Гитлер разорвал Версальский договор, на военный флот было наложено много жестких ограничений. Кораблей было мало, к тому же все они были устаревшими, так что перспектива карьеры была далеко не блестящей. Однако Хинтце жадно хватался за каждую представившуюся возможность — он прошел курс подготовки в морском училище (Marineschule Flensburg-Mürwik), затем, уже во время флотской службы, в 1920 году плавал на тральщиках, торпедных катерах и старых легких крейсерах «Аркона» и «Амазон», которые были построены еще до начала века и которые победители великодушно разрешили Германии сохранить. Первая возможность плавать на одном из новых кораблей представилась в 1932 году, когда Хинтце получил звание капитана-лейтенанта и был назначен командиром торпедной части 6000-тонного крейсера «Кёльн», спущенного на воду три года тому назад. Его последующие назначения были так или иначе связаны с сушей вплоть до 1938 года, когда он оказался на борту крейсера «Эмден» в качестве его капитана и штурмана. Через несколько месяцев, после обучения на курсах штабных офицеров в 1939 году, он был назначен штурманом новейшего тяжелого крейсера «Адмирал Хиппер» (водоизмещением 18 000 тонн), который был вооружен восемью 8-дюймовыми орудиями и развивал скорость до 33 узлов.
«Мой крестный очень любил семью,
— говорит фрау Вольтерсдорф. —
Он часто навещал мою мать и свою сестру, и я помню, как мы гордились им и радовались его [успехам] в карьере».
В звании фрегатен-капитана (капитана 2 ранга), начиная с 1940 года, Хинтце плавал по всем морям от Шпицбергена на севере и до Африки на юге, выполняя обязанности штурмана у двух капитанов — сначала у капитана цур зее Германа Хейе, а затем — у капитана цур зее Вильгельма Майзеля. Он получил опыт плавания в условиях свирепых ветров в Норвежском море, а также штормов и обледенения в Датском проливе. Крещение огнем произошло у норвежских берегов, во время немецкого нападения на Тронхейм 9 апреля 1940 года; в этот день «Хиппер» потопил английский эсминец «Глоууорм», который в ходе короткого и кровопролитного боя пытался протаранить крейсер. В декабре 1940 года Хинтце вновь оказался в центре событий, когда его корабль вступил в бой с британским крейсером «Бервик», что произошло во время первого выхода «Хиппера» в Атлантику. Немецкий крейсер получил повреждения, а корабль союзников затонул. Следующий рейд, который был предпринят в феврале 1941 года, оказался более успешным. Недалеко от Мадейры «Хиппер» натолкнулся на конвой, который шел без прикрытия; вскоре семь транспортов были пущены на дно, а еще три получили серьезные повреждения. Затем семь месяцев продолжалось докование в Германии, и лишь после этого Хинтце вновь вернулся в Арктику. «Хиппер» был в составе отряда, который в июле 1942 года вышел из Альта-фьорда для того, чтобы атаковать конвой PQ-17, однако атака не состоялась, потому что флотилия была отозвана обратно. В конце лета 1942 года Хинтце был повышен в звании и стал капитаном цур зее, его назначили командиром Экспериментальной торпедной базы в Эккерн-фьорде, недалеко от Киля; теперь у него за плечами были три драматичных года, заполненных захватывающими событиями. Они дали ему богатый опыт боевой службы на крупных кораблях, а это означало, что его временное пребывание в Эккерн-фьорде было лишь промежуточной остановкой. Осенью 1943 года Хинтце узнал, что назначен капитаном линкора «Шарнхорст»; он не сомневался, что на это назначение благословили его прежние командиры на «Хиппере» Хейе и Майзель; оба в настоящее время были произведены в адмиралы и направлялись на ответственную штабную работу. Хейе стал начальником штаба группы «Норд» в Киле, а Майзель — начальником штаба Главного командования Кригсмарине (Oberkommando der Kriegsmarine — OKM) в Берлине.
После этого назначения мечта всей жизни Хинтце осуществилась полностью. Вспоминая прошлое, Карин Вольтерсдорф рассказывает:
«Для него было большим счастьем — командовать одним из самых крупных и лучших кораблей военно-морского флота. Но он прекрасно понимал, что это — нелегкая задача, потому что знал о комплексе неполноценности Германии как морской державы и хорошо представлял трудности, связанные с его новой работой. Перед отъездом на Север он приехал к нам. Был холодный день октября 1943 года. Обычно наши встречи бывали веселыми и теплыми, но на этот раз мы прощались с ним, испытывая глубокую грусть. Мой крестный хорошо представлял, что его ждет, и это его совершенно не радовало».