После окончания военных действий поступил приказ демобилизовать флот, а Тегетгофф сдал командование действующей эскадрой. Увы, для 39-летнего вице-адмирала просто не существовало подходящей должности. Так как предполагалось, что позднее он станет главнокомандующим австрийским флотом, было решено отправить Тегетгоффа в поездку по главным морским державам. Навестив свою мать, живущую в Граце, 27 сентября 1866 года он отправился в путешествие. 3 декабря Тегетгофф прибыл в Лондон. Он посетил несколько верфей, осмотрел в Ливерпуле гигантский пароход «Грейт Истерн» и 19 декабря отплыл в Нью-Йорк. В Соединенных Штатах Тегетгофф побывал в Ниагаре, Филадельфии, Вашингтоне, Аннаполисе, Чарлстоне, Мобиле, Новом Орлеане, Питтсбурге и Норфолке. Во время путешествия он воочию оценил разрушительные последствия Гражданской войны. В апреле 1867 года Тегетгофф вернулся в Европу.
Во время пребывания в Париже в дни Всемирной выставки Тегетгофф получил телеграфный приказ немедленно вернуться в Австрию. Восставшие мексиканцы захватили и расстреляли императора Максимилиана. Франц-Иосиф поручил Тегетгоффу деликатную миссию доставить останки Максимилиана на родину.
В сопровождении своего брата, армейского полковника, Тегетгофф 10 июля отправился в Мексику и прибыл туда 26 августа. Сначала мексиканцы отказались выдать тело Максимилиана. После долгих переговоров, в ходе которых адмирал проявил большое дипломатическое искусство, Тегетгофф добился своего. В конце года тело бывшего командующего австрийским флотом было доставлено на родину паровым фрегатом «Новара». Тегетгофф вернулся на том же корабле.
Тегетгофф прибыл в Вену 17 января 1868 года и сразу получил задание подготовить план реорганизации флота. Он хотел создать независимое морское министерство, однако этому воспротивились представители Венгрии, континентальной части Двуединой Монархии, в которую превратилась Австрийская империя в 1867 году. После этого Тегетгофф рекомендовал создать ответственный военно-морской департамент в рамках военного министерства. Его предложения были приняты 25 февраля 1868 года. Тегетгофф был назначен начальником морского департамента и занялся реорганизацией флота. Он получил право прямого доступа к императору,[38] в результате чего за состояние флота адмирал отвечал только перед императором, а не перед военным министром. Однако именно военный министр представлял флот перед парламентскими делегациями обоих частей империи, в частности — при обсуждении бюджетных вопросов. Сложилась крайне неудачная система, в которой Тегетгофф не имел прямого влияния на вопросы бюджета, но все-таки полностью отвечал за боеспособность флота. В результате возникали многочисленные трения, подтачивали физические силы и разрушали нервную систему. Все командующие австрийским флотом поочередно оказывались под этим жутким бюрократическим прессом.
Несмотря на все препятствия, Тегетгофф сумел провести несколько важных реформ. До сих пор организация флота восходила к эпохе парусных кораблей, когда абордажные партии комплектовались из морских пехотинцев и существовал отдельный корпус морской артиллерии. Тегетгофф упростил организационную структуру и ликвидировал многие специальные службы. В будущем орудия должны были обслуживать матросы, прошедшие специальное обучение на борту учебных артиллерийских кораблей (обычно старых броненосцев). Тегетгофф также ликвидировал разделение ответственности при принятии важных решений. Раньше требовалось собрать целую коллекцию подписей от различных департаментов по вопросу, который можно было решить силами одного из них. В результате за решение проблемы не отвечал никто. Теперь, почти в каждом случае, каждый департамент отвечал за свой участок работы. «Битва за ответственность» больно ударила по чиновникам. Теперь шансы на продвижение по служебной лестнице имели только те офицеры, которые были готовы отвечать за свои действия.
Во время споров о путях реорганизации системы обороны империи Тегетгофф яростно отстаивал ликвидацию береговых укреплений и ратовал за создание сильного мобильного флота. Он соглашался укреплять только главную военно-морскую базу Пола и построить несколько береговых батарей для прикрытия гавани Фазана. Тегетгофф показал себя знающим экономистом и умелым администратором. С помощью своих реформ он сумел сократить численность личного состава флота в мирное время почти на 2000 человек. Тем не менее, он не сумел добиться своей цели и построить флот из 15 броненосцев. Тегетгофф не сумел преодолеть сопротивление армии, которая предпочитала строить береговые укрепления, хотя бой у Лиссы ясно показал преимущества мобильного флота перед береговыми батареями.
