Steinbach absolvierte Studien am Leipziger Konservatorium sowie bei Gustav Nottebohm (Theorie und Kontrapunkt) und Anton Door (Klavier) in Wien. Wie vor ihm Max Bruch und Engelbert Humperdinck wurde der 19-Jährige 1874 Stipendiat der Frankfurter Mozart-Stiftung.

Obwohl er anfänglich eine Komponisten-Laufbahn angestrebt hatte, etablierte sich Steinbach ab ca. 1879 zunehmend als Dirigent.

Nach einer ersten Anstellung als 2. Kapellmeister in Mainz, begleitete er ab 1886 17 Jahre lang das Amt des Meininger Hofkapellmeisters. Ihm gelang es, die von Bülow erarbeitete Stellung der Brahms'schen Werke in der Konzertkultur enorm auszubauen.

Steinbach war zwischen 1853 und 1902 nicht nur zahlenmäßiger Spitzenreiter unter den Brahms-Interpreten und damit ein wesentlicher Impulsgeber der europäischen Brahms-Rezeption um 1900.

Er galt auch über seinen Tod hinaus international als einer der besten Brahms-Dirigenten. Die von ihm initiierten Landesmusikfeste 1895 und 1899 ließen Meiningen zu einem Mekka der Brahms-Kenner und -Liebhaber werden.

An der Errichtung des ersten Brahms-Denkmals im Oktober 1899 war er wesentlich beteiligt.

Prägend für seine Amtszeit wurden ebenfalls große chorsinfonische Konzerte unter Einbeziehung von Ensembles aus dem gesamten Herzogtum. So leitete er z. B. die Meininger Erstaufführung von Johann Sebastian Bachs "Matthäus-Passion" (1890).

Auch mit der Edition der Brandenburgischen Konzerte machte er sich um die Bachpflege verdient.

Nachdem die Realisierung des ambitionierten Planes der Errichtung einer Brahms-Konzerthalle mit angeschlossenem Konservatorium im Englischen Garten nicht gelang, folgte er 1903 dem Ruf an das Kölner Gürzenich-Orchester und wurde zugleich Direktor des Kölner Konservatoriums, wo er u. a. den Komponisten Erwin Schulhoff und den Dirigenten Fritz Busch unterrichtete.