Im Jahre 1855 galt Tegetthoff für einen der besten Marineoffiziere und übernahm deswegen den Dampfer Taurus, mit dem er entlang Konstantinopel bis zur Donaumündung segelte. Hier verankerte er das Schiff in Sulina, als es in der Zeit des Krimkrieges zwischen dem osmanischen Reich, Großbritannien, Frankreich und Piemont auf der einen Seite und Russland auf der anderen um die Oberherrschaft über die Mittelmeerengen gekämpft wurde. Die Donau war als die zentrale Flusstransversale für den österreichischen Handel von großer Bedeutung und Tegetthoff sorgte für die Berücksichtigung der Habsburger Interessen. Für seine umfangreiche Berichte und wirksame Ordnungsschaffung erhielt er 1856 mit dem Lob des Oberbefehlshabers der österreichischen Marine, des Erzherzogs Ferdinand Max, eine große Anerkennung. In den Jahren 1857 und 1858 schickte man ihn auf eine der ersten österreichischen forschungspolitischen Expeditionen in den Nahen Osten. Auf die Expedition auf dem Roten Meer und in dem Golf von Aden, wo Österreich nach möglichen Kolonialisierungsterritorien und nach dem geeigneten Ort für die Herstellung einer Kohlenstation suchte, segelte er mit dem Forscher Martin Theodor von Heuglin.
Im Jahre 1858, als sein Vater starb, bekam er die erste wichtige Beförderung zum Korvetten-Kapitän und zum Leiter der ersten Sektion am Marineoberkommando in Triest. Schon im Oktober 1858 segelte er als Korvettenkapitän nach Marokko, wo er die österreichischen Handelsinteressen schützte.
Seine Reiseberichte, in denen er beharrlich die Empfehlungen und Vorschläge für die Marinereorganisation niederschrieb, hinterließen beim Erzherzog Ferdinand Max einen starken Eindruck und deswegen begleitete Tegetthoff ihn als Adjutant des Marineoberbefehlshabers in den Jahren 1859 und 1860 auf der Reise nach Brasilien. Nach dieser Reise wurde er Fregattenkapitän. Im nächsten Jahr wurde er zum Kapitän eines Linienkampfschiffes befördert. Im Oktober 1862 wurde er zum Kommandeur der Fregatte Novara, des Symbols der österreichischen Kriegsmarine, ernannt; im November 1862 übernahm er das Kommando der österreichischen Flotte, die im östlichen Mittelmeer die griechische Krise beaufsichtigte.