A ideia saiu de uma conversa num jogo de basebol, em meados dos anos setenta. Robert Hayden acabara de entrar como director-geral da Sierra Bullets —outra marca que distribuímos— e Frank Snow, antigo proprietário da Sierra, tornara-se seu amigo durante a transferência. Nessa noite decidiram entrar no negócio dos estojos. Juntaram Paul Knepp, fabricante de matrizes da Sierra, compraram maquinaria militar excedente e instalaram-na num pavilhão de chapa alugado em Covina, Califórnia. A Starline Brass foi constituída em 1976: Snow fornecia as máquinas, Knepp as ferramentas e Hayden as vendas.

O primeiro estojo foi o .38 Special, seguido do .45 ACP e do 10 mm Auto. Durante anos a casa não vendeu com o próprio nome: estampava culotes por encomenda para Remington, Winchester, Federal e Midway Arms. A viragem chegou com o contrato do FBI para o 10 mm ganho pela Federal, quando a Starline passou a fabricar 750.000 estojos por mês só para o cumprir.

Hayden viu então a abertura. Disputar o 9 mm com fábricas que o fazem aos milhões não fazia sentido; fazer cartuchos que ninguém produzia, sim. A casa propôs-se fabricar tantos calibres diferentes quantos pudesse —mais de setenta e cinco— e no início dos anos oitenta estampou a própria estrela e começou a vender directamente. Dessa decisão vem a possibilidade actual de recarregar um .38 Short Colt, um 7,65 French Long ou o 9 mm Largo de uma Star ou Astra.

Em 1992 mudou-se para Sedalia, Missouri, para ampliar a fábrica e escapar ao clima industrial da Califórnia. Continua a ser uma empresa familiar, dirigida por Robert Hayden Jr.