Прежде чем обратиться в 1856 году к естественным наукам, Штейндахнер изучал право в Вене. Он занимался сначала ископаемыми рыбами. За свои выдающиеся труды в 1860 году ему было поручено возглавить коллекцию рыб Музея естествознания в Вене. В следующем году, после ухода Леопольда Фитцингера, он также принял коллекцию земноводных и пресмыкающихся.
Первые путешествия привели Штейндахнера в Испанию, Португалию, на Канарские острова и в Сенегал.
С 1859 по 1868 годы Штейндахнер опубликовал 55 трудов по ихтиологии, что составило в общей сложности почти 900 страниц, и стал за короткое время одним из самых выдающихся ихтиологов. В 1890-х годах он возглавил Австро-Венгерскую глубоководную экспедицию в восточной части Средиземного, в Адриатическом и Красном морях.
Род рыб Steindachneridion (семейство Pimelodidae) назван в его честь.