Nascido no Brooklyn, Nova York, em 1917, filho de pais imigrantes da Varsóvia, na Polônia, e Riga, na Letônia, Steinweiss foi contratado em 1939 para desenhar anúncios para o selo Colúmbia. Contudo, logo de início passou a desenhar capas originais e coloridas para os discos. Até então eles eram negros ou marrons e pareciam álbuns de fotos. Dai o fato de serem chamados "álbuns".
A primeira ilustração de Steinweiss foi para um disco de Rodgers e Hart, no qual ele reproduziu a entrada de um teatro em Nova York com os nomes dos artistas em letras luminosas.
