Затем Тегетгоффа назначают командиром колесного парохода «Таурус», который представляет австрийские интересы в Сулине, принадлежащем Турции порту в устье Дуная на Черном море. Обеспечение свободного плавания по великой европейской реке имело жизненно важное значение для австрийской экономики, а последствия Крымской войны привели к анархии в Сулине. С января 1856 по январь 1857 года Тегетгофф командует стационером, при этом он действует энергично и без лишних церемоний, внеся основной вклад в нормализацию обстановки. Действия Тегетгоффа получили высокую оценку начальства. Турецкое правительство награждает его орденом Меджидие, однако Тегетгоффа тут же подстерегает и разочарование. Его надеждам совершить кругосветное плавание на фрегате «Новара» не суждено сбыться.

После возвращения из Сулина Тегетгофф представляет подробный рапорт командующему флотом эрцгерцогу Фердинанду-Максимилиану, 24-летнему брату императора Франца-Иосифа. После короткого отпуска Тегетгофф получает новое деликатное задание. Он должен отыскать подходящее место для базы на Красном море, которое приобретет огромное значение для торговли с азиатскими странами после завершения постройки Суэцкого канала. Первую часть путешествия Тегетгофф проделал вместе с вице-консулом фон Хеглином. Они поднимаются по Нилу до Луксора а потом пересекают пустыню и прибывают в Козер на берегу Красного моря. Там австрийцы арендуют парусное судно и плывут в Аден, где фон Хеглин и остается. Дальше Тегетгофф путешествует один. Он посещает остров Сокотра, который кажется ему наиболее подходящим для создания военно-морской базы, и Берберу, после чего возвращается в Аден. В марте 1857 года он возвращается в Триест. Из-за тайного характера миссии Тегетгофф не может получить орден, однако его производят в капитан-лейтенанты и назначают начальником первого отдела штаба флота. Этот отдел был самым большим из трех и отвечал за оперативные планы, личный состав, правосудие, медицинскую службу, учебу и морскую пехоту.[34] В качестве начальника первого отдела Тегетгофф становится заместителем командующего флотом.

Пребывание Тегетгоффа на берегу не затянулось. 24 октября 1858 года он становится командиром корвета «Эрцгерцог Фридрих», на котором совершает плавание в Марокко. После того как в воздухе запахло порохом, в феврале 1859 года корвет возвращается домой. Снова противником Австрии оказалась Сардиния, на сей раз в союзе с Францией. Против значительно превосходящих сил противника молодой австрийский флот ничего не мог сделать и оставался пассивным. На суше Австрия потерпела поражение и потеряла одну из итальянских провинций — Ломбардию. В 1860 году было провозглашено создание Королевства Италия. Однако объединение Италии осталось незавершенным, так как Австрия все еще удерживала провинцию Венеция.

После войны Тегетгофф некоторое время прослужил на берегу, а потом сопровождал эрцгерцога Фердинанда-Макса в ботанической экспедиции в Бразилию. Он отплыли из Триеста в ноябре 1859 года на колесном пароходе «Кайзерин Элизабет» и вернулись в Адриатику в конце марта 1860 года. После этого Тегетгофф получает первый отпуск длиной в месяц. Одновременно его производят в капитаны 2 ранга.

После возвращения на службу Тегетгофф становится командиром винтового фрегата «Радецкий». Его направляют в Сирию защищать там австрийские интересы. После недолгого ремонта на верфи в Поле «Радецкий» переходит в бухту Каттаро. Фрегат крейсирует в южной Адриатике, чтобы помешать контрабанде оружия из Италии на мятежные Балканы. Он возвращается в Полу в октябре 1861 года, и Тегетгофф сдает командование. Большую часть 1862 года он проводит в штабе флота и играет важную роль в реформе этого учреждения, которую проводит эрцгерцог Фердинанд-Макс.

В октябре 1862 года Тегетгофф становится командиром дивизии, состоящей из винтового фрегата «Новара», корвета «Эрцгерцог Фридрих» и канонерок «Велебит» и «Валь». Одновременно Тегетгофф является и командиром «Новары». Дивизия направляется в Грецию, чтобы защитить австрийские интересы во время мятежа против короля Оттона. Исключительно точные рапорты Тегетгоффа с оценкой событий получают полное одобрение эрцгерцога Фердинанда-Макса. В течение всей службы Тегетгофф показывает глубокое понимание политической, социальной и экономической ситуации и дает совершенно правильные оценки событий.

Когда в ноябре 1863 года «Новара» становится на верфь для ремонта, Тегетгофф назначается командиром винтового фрегата «Шварценберг». В декабре он начинает плавание по Восточному Средиземноморью, посещает Александрию, Абукир и следит за ходом работ на Суэцком канале. Вскоре после этого долго тянувшиеся споры между Данией и Германской Конфедерацией относительно статуса провинций Шлезвиг и Гольштейн[35] приводят к войне. Тегетгофф узнает о начале кризиса в Бейруте и немедленно направляется домой. На Корфу он получает приказ следовать в Лиссабон и ожидать там прибытия австрийской эскадры, сформированной для действий в Северном море.

1 февраля 1864 года германские и австрийские войска пересекают реку Эйдер, чтобы обеспечить переход спорных провинций к Германской Конфедерации. Дания немедленно начинает блокаду немецкого побережья. Так как германский флот был слишком слаб, чтобы сражаться с датчанами, было принято решение послать на театр военных действий австрийскую эскадру под командованием бывшего командира Тегетгоффа барона фон Вюллерсдорф-Урбера.

Тем временем Тегетгофф прибывает в Лиссабон на «Шварценберге». В начале апреля 1864 года к нему присоединяется «Радецкий». Так как подготовка эскадры затянулась, Тегетгофф получил приказ следовать в Северное море всего с 2 фрегатами. После коротких заходов в Брест и Даунс для приемки угля, 4 мая он прибывает в Куксхафен.

Англичане информировали датчан о всех передвижениях австрийских кораблей. И их прибытия уже ожидала эскадра коммодора Свенсона в составе винтовых фрегатов «Нильс Юэль» и «Ютланд» и винтового корвета «Хеймдаль». Узнав, что датская эскадра находится недалеко от острова Гельголанд, Тегетгофф немедленно выходит в море с обоими фрегатами и 3 прусскими канонерками. В результате 9 мая вблизи от Гельголанда произошел бой. В течение нескольких часов австрийские корабли упорно сражались против более сильной вражеской эскадры. Наконец загорелась фок-мачта «Шварценберга», что вынудило Тегетгоффа выйти из боя. После того как пожар был потушен, он вернулся в Куксхафен. Датчане тоже покинули Северное море, узнав о подписании перемирия. Блокада Германии закончилась.

На следующий день император произвел Тегетгоффа в контр-адмиралы и наградил его орденом Железной Короны второго класса. Несмотря на обрушившиеся на него почести, Тегетгофф остался скромным человеком. Он говорил, что успех принесло мужество его офицеров и матросов.

В середине мая эскадра Вюллерсдорф-Урбера добралась до Северного моря и пробыла там до сентября. Несмотря на то, что летом перемирие закончилось, флоты противников больше не встречались. На суше Дания потерпела поражение и 1 августа запросила мира. 21 сентября Тегетгофф отплыл в Австрию. По условиям мирного договора, подписанного через месяц, Дания передала Шлезвиг и Гольштейн Германской Конфедерации. В ходе войны Тегетгофф показал, что готов принять на себя ответственность, и всегда толковал приказы штаба флота таким образом, который предоставлял ему наибольшую свободу действий. Хотя с тактической точки зрения бой у Гельголанда не стал австрийской победой, его результат и последующее прибытие главной австрийской эскадры привело к снятию блокады и возобновлению морской торговли. В результате Тегетгофф стал первым немецким героем-моряком нового времени, причем его уважали не только в Австрии, но и в северной Германии.