Après des études musicales auprès d'Hermann Abendroth au Conservatoire de Cologne, il devient en 1924 l'assistant d'Otto Klemperer à l'Opéra de Cologne. De 1925 à 1929, il dirige l'Opéra de Prague, puis celui de Francfort de 1929 à 1933.
Démis par les nazis en raison de ses origines juives, il quitte l'Allemagne en 1936 et rejoint la Palestine, future Israël. Avec Bronisław Huberman, il fonde et dirige en 1936 l'Orchestre symphonique de Palestine (futur Orchestre philharmonique d'Israël) jusqu'en 1938, date à laquelle il rejoint les États-Unis. Arturo Toscanini, qui avait apprécié le travail de Steinberg avec l'Orchestre symphonique de Palestine, l'engage comme assistant à l'Orchestre symphonique de la NBC.
Il conduit l'Orchestre philharmonique de Buffalo de 1945 à 1953, l'Orchestre symphonique de Pittsburgh de 1952 à 1976. Il dirige également l'Orchestre philharmonique de Londres de 1958 à 1960. En 1962, pressenti pour succéder à Charles Münch à la tête du prestigieux Orchestre symphonique de Boston, c'est finalement Erich Leinsdorf qui lui est préféré. Néanmoins, Steinberg sera fréquemment invité à Boston avant de succéder finalement à Leinsdorf en 1969. Il emmène l'orchestre en tournée en Europe en 1971, mais doit abandonner son poste en 1972 pour des raisons de santé.
Chef éclectique, il dirigea un grand nombre de pièces de son temps, entre autres de plusieurs compositeurs américains : Aaron Copland, William Schuman, Roy Harris, Heitor Villa-Lobos, sans pour autant négliger les compositeurs de la première moitié du vingtième siècle (Stravinsky, Berg, Bartok...) ainsi que la musique romantique et post-romantique allemande, en particulier Anton Bruckner, Richard Strauss et Gustav Mahler. Il portait également une affection particulière pour les œuvres d'Edward Elgar et Ralph Vaughan Williams.
