Euclides Zenóbio da Costa era neto e filho de militares. Seu pai, o General de Divisão José Zenóbio da Costa, foi Diretor do Arsenal de Guerra de Mato Grosso. Ingressou no Colégio Militar do Rio de Janeiro no ano de 1903. Assentou praça em 30 de dezembro de 1911, no 2º Regimento de Cavalaria Divisionária. Aspirante a Oficial em 1915, participou da repressão à Revolta do Contestado, na divisa de Santa Catarina e Paraná. Prosseguiu seus estudos na Escola Militar do Realengo, onde concluiu os cursos de Infantaria e Cavalaria, em 1916.
Galgou promoções ao longo da carreira como oficial, até ser promovido a General de Brigada, em 29 de agosto de 1941, sendo nomeado Comandante da 8ª Região Militar, em Belém (PA). Já em 1943, após a declaração de guerra do Brasil aos países do Eixo, voluntariou-se para a FEB, sendo designado para comandar a Infantaria Divisionária.
O General Zenóbio da Costa partiu no primeiro escalão de embarque rumo a terras italianas, em 2 de julho de 1944, no navio-transporte General Mann, da Marinha dos Estados Unidos, com aproximadamente 5.075 militares. Como Comandante da Infantaria Divisionária, tinha sob sua subordinação as tropas do 1º, 6º e 11º Regimentos de Infantaria.
A FEB ficou subordinada ao V Exército Americano, finalizando os preparativos para entrar em ação na localidade de Tarquínia. Desde os primeiros contatos com o inimigo, em 16 de setembro de 1944, até a rendição da 148ª Divisão Alemã, em Fornovo di Taro, no dia 28 de abril de 1945, o General Zenóbio da Costa manteve-se sempre próximo de sua tropa.
Assumiu pessoalmente a chefia das operações na Tomada de Monte Castello, em 21 de fevereiro de 1945, mais célebre vitória da FEB. A partir dali, tomou Castelnuovo, Montese, Zocca, Montalto, Vignola, Marano e Collechio, alcançando Turim em 1º de maio, na véspera da rendição alemã em toda a frente italiana. No dia 9 de maio de 1945, foi promovido a General de Divisão. No mês seguinte, representou o Exército Brasileiro na Parada da Vitória, realizada em Londres.
Idealizador da criação da Polícia do Exército, sendo seu Patrono, foi Ministro da Guerra durante o segundo governo do presidente Getúlio Vargas (1951-1954). Faleceu no dia 29 de setembro de 1963, no Rio de Janeiro.