В апреле 1854 года Тегетгофф уже в звании лейтенанта покидает «Каролину» и 13 июля становится командиром своего первого корабля — шхуны «Элизабет». Этот корабль большей частью плавал в Адриатическом и Ионическом морях, иногда заходя в Бейрут. Тегетгофф сдает командование «Элизабет» в ноябре 1855 года и получает прекрасную служебную характеристику от командира Левантийской эскадры. В этот период Тегетгофф изучает турецкий язык.
Затем Тегетгоффа назначают командиром колесного парохода «Таурус», который представляет австрийские интересы в Сулине, принадлежащем Турции порту в устье Дуная на Черном море. Обеспечение свободного плавания по великой европейской реке имело жизненно важное значение для австрийской экономики, а последствия Крымской войны привели к анархии в Сулине. С января 1856 по январь 1857 года Тегетгофф командует стационером, при этом он действует энергично и без лишних церемоний, внеся основной вклад в нормализацию обстановки. Действия Тегетгоффа получили высокую оценку начальства. Турецкое правительство награждает его орденом Меджидие, однако Тегетгоффа тут же подстерегает и разочарование. Его надеждам совершить кругосветное плавание на фрегате «Новара» не суждено сбыться.
После возвращения из Сулина Тегетгофф представляет подробный рапорт командующему флотом эрцгерцогу Фердинанду-Максимилиану, 24-летнему брату императора Франца-Иосифа. После короткого отпуска Тегетгофф получает новое деликатное задание. Он должен отыскать подходящее место для базы на Красном море, которое приобретет огромное значение для торговли с азиатскими странами после завершения постройки Суэцкого канала. Первую часть путешествия Тегетгофф проделал вместе с вице-консулом фон Хеглином. Они поднимаются по Нилу до Луксора а потом пересекают пустыню и прибывают в Козер на берегу Красного моря. Там австрийцы арендуют парусное судно и плывут в Аден, где фон Хеглин и остается. Дальше Тегетгофф путешествует один. Он посещает остров Сокотра, который кажется ему наиболее подходящим для создания военно-морской базы, и Берберу, после чего возвращается в Аден. В марте 1857 года он возвращается в Триест. Из-за тайного характера миссии Тегетгофф не может получить орден, однако его производят в капитан-лейтенанты и назначают начальником первого отдела штаба флота. Этот отдел был самым большим из трех и отвечал за оперативные планы, личный состав, правосудие, медицинскую службу, учебу и морскую пехоту.
[34]В качестве начальника первого отдела Тегетгофф становится заместителем командующего флотом.Пребывание Тегетгоффа на берегу не затянулось. 24 октября 1858 года он становится командиром корвета «Эрцгерцог Фридрих», на котором совершает плавание в Марокко. После того как в воздухе запахло порохом, в феврале 1859 года корвет возвращается домой. Снова противником Австрии оказалась Сардиния, на сей раз в союзе с Францией. Против значительно превосходящих сил противника молодой австрийский флот ничего не мог сделать и оставался пассивным. На суше Австрия потерпела поражение и потеряла одну из итальянских провинций — Ломбардию. В 1860 году было провозглашено создание Королевства Италия. Однако объединение Италии осталось незавершенным, так как Австрия все еще удерживала провинцию Венеция.
После войны Тегетгофф некоторое время прослужил на берегу, а потом сопровождал эрцгерцога Фердинанда-Макса в ботанической экспедиции в Бразилию. Он отплыли из Триеста в ноябре 1859 года на колесном пароходе «Кайзерин Элизабет» и вернулись в Адриатику в конце марта 1860 года. После этого Тегетгофф получает первый отпуск длиной в месяц. Одновременно его производят в капитаны 2 ранга.
После возвращения на службу Тегетгофф становится командиром винтового фрегата «Радецкий». Его направляют в Сирию защищать там австрийские интересы. После недолгого ремонта на верфи в Поле «Радецкий» переходит в бухту Каттаро. Фрегат крейсирует в южной Адриатике, чтобы помешать контрабанде оружия из Италии на мятежные Балканы. Он возвращается в Полу в октябре 1861 года, и Тегетгофф сдает командование. Большую часть 1862 года он проводит в штабе флота и играет важную роль в реформе этого учреждения, которую проводит эрцгерцог Фердинанд-Макс.
В октябре 1862 года Тегетгофф становится командиром дивизии, состоящей из винтового фрегата «Новара», корвета «Эрцгерцог Фридрих» и канонерок «Велебит» и «Валь». Одновременно Тегетгофф является и командиром «Новары». Дивизия направляется в Грецию, чтобы защитить австрийские интересы во время мятежа против короля Оттона. Исключительно точные рапорты Тегетгоффа с оценкой событий получают полное одобрение эрцгерцога Фердинанда-Макса. В течение всей службы Тегетгофф показывает глубокое понимание политической, социальной и экономической ситуации и дает совершенно правильные оценки событий.