O estádio havia passado para a propriedade do Vitória há, mais ou menos, cinco anos. Apesar disso, não tinha recebido qualquer nome, passando a ser simplesmente o Estádio do Vitória Sport Clube.
Por isso, naquela Assembleia-Geral de final da temporada 1994/95, foi apresentada pelo presidente da Assembleia-Geral, José Cotter, a seguinte proposta: " Critérios com vista à aprovação da nova denominação do estádio". Para que tal decorresse dentro da maior elevação, pediu a maior dignidade para aprovação de tal ponto. Além disso, deu como data limite para apresentar propostas de nomenclatura até ao dia 15 de Setembro, devendo estas ser subscritas por, pelo menos, 200 associados. Depois, no dia 23 de Setembro, deveria ocorrer uma votação secreta, sendo que se nenhuma das propostas apresentadas obtivesse 50%+1 dos votos expressos, deveria ocorrer uma segunda volta entre as duas propostas mais votadas uma semana depois.
Imediatamente surgiram alguns nomes: o do Presidente Pimenta Machado que, imediatamente rejeito tal hipótese por "Salazar teve o seu nome em Ruas, Avenidas, Estádios, Pontes e até Estátuas. Mas, depois, cortaram-lhe a cabeça nessas mesmas estátuas e riscaram o seu nome em outros locais.", para além de José Maria Castro Ferreira (o presidente da Câmara, dinamizador do estádio 40 anos antes) e D.Afonso Henriques. A estes, posteriormente, juntou-se o de Estádio da Amorosa, em alusão ao anterior recinto onde o Vitória tivera tantas alegrias, bem como o de Estádio do Vitória Sport Clube.
Na votação de 23 Setembro, nenhuma das propostas teve a maioria, sendo que a mais votada era a da alusão anterior que o recinto possuía: Estádio Vitória Sport Clube com 280 votos. A passar à segunda volta com esta, com 267 votos, a designação de Estádio D.Afonso Henriques.
Nesse segundo acto, a denominação de Estádio D.Afonso Henriques venceria por 95 votos, dando a entender que quem tinha votado nos outros nomes, coligou-se em favor da proposta que defendia o nome do Rei fundador. Contou com 453 manifestações de aprovação contra 358 de Estádio do Vitória Sport Clube.
Depois de terem sido conhecidos os resultados do escrutínio, António Mendes, durante vários anos responsável pelo departamento de futebol do clube e o subscritor número um do nome vencedor, dizia que "foi uma vitória do Vitória. Da sua massa associativa e ficou provado que o nome de D.Afonso Henriques era o nome adequado para o estádio, contrariamente ao que pessoas responsáveis, mas sem sentimentos, afirmavam."
E até hoje, o estádio do Clube do Rei possui um nome em consonância com o seu emblema e com uma história que tanto o orgulha.