À área inicial foi mais tarde adicionado um terreno contíguo de 23 hectares concedido ao CFVM pelas autoridades municipais da Matola, que visava um mais desenvolto planeamento de parques para automóveis e um arranjo urbanístico mais conseguido da zona. Para esta concessão, muito contribuíram as influências do Almirante Manuel Maria Sarmento Rodrigues e do Comandante Vasco da Gama Rodrigues, respectivamente governadores geral de Moçambique e do distrito de Lourenço Marques.
Adquirido o terreno, o Conselho de Administração dos Caminhos de Ferro de Moçambique, de que era então Administrador-Delegado o engenheiro Horácio Avelino Brazão de Freitas, naquilo que foi considerado uma manifestação sem par na história da empresa, aprova a 10 de Abril de 1962, pela sua deliberação N o 227, o anteprojecto do estádio e concede ao CFVM a primeira tranche financeira para o arranque das obras. Em finais de 1962, ficaram concluídos os trabalhos de topografia necessários à elaboração do projecto definido para a implantação da obra e, em 29 de Junho de 1963, foi iniciada a terraplanagem do local, num trabalho necessariamente esgotante e moroso e para o qual, de acordo com as crónicas da época, se escolheu pessoal dedicado que, à oferta do seu esforço, juntasse o espírito de sacrifício e entusiasmo.
Aos esforços hercúleos, os ferroviários, sobretudo amassa associativa do CFVM, conscientes da grandeza da obra que se ia erguer e da sua utilidade em benefício do Desporto em Moçambique, adicionaram a sua generosidade contribuindo com uma quotização mensal suplementar, para além de organizar várias manifestações, nomeadamente, quermesses, churrascos, representações, serões musicais, festas, rifas e outras, para a angariação de fundos. Em meados de 1965, sempre com o interesse e o estímulo, quer do governo, quer do Conselho de Administração dos CFM e dos dirigentes do desporto em Moçambique, expressos através de palavras e do próprio acompanhamento das obras, iniciou-se a construção das bancadas sob a orientação do chefe do serviço de via e obras, o Eng. Domingos Vaz, e foi lançada a relva sobre o espaço projectado para ser o rectângulo do jogo..
A 29 de Maio de 1966, a obra que prosseguia sem quaisquer desfalecimentos é visitada pelo Governador- Geral Costa Almeida e, a 6 de Outubro do mesmo ano, a Assembleia-Geral do CFVM, por aclamação decide atribuir ao seu empreendimento o nome de Estádio Salazar, em homenagem ao chefe do governo português, António de Oliveira Salazar. E, em Junho de 1967, é o ministro do Ultramar, Silva Cunha, que ao visitar Moçambique, procede ao fecho simbólico das bancadas do 1°anel do estádio, as mesmas que permanecem até aos nossos dias. 1967 foi também o ano em que estando as obras na fase dos acabamentos, o CFVM decidiu marcar para 30 de Junho de 1968 como a data de inauguração do estádio, ao qual se seguiu a constituição de uma comissão incumbida de organizar o programa da cerimónia da inauguração, de forma a corresponder ao valor da obra e ao nome do seu patrono.
Uma das primeiras iniciativas da comissão foi a de, com autorização da Federação Portuguesa de Futebol, convidar o Brasil a comparticipar na cerimónia com a sua selecção nacional "A" de futebol, que defrontaria a sua congénere de Portugal, uma reedição da partida disputada entre as duas equipas na fase final da Taça do Mundo de 1966 na Inglaterra, na qual os portugueses derrotaram os seus irmãos do outro lado do Atlântico por 3-1, numa tarde de glória dos moçambicanos Eusébio da Silva Ferreira, Mário Esteves Coluna, Vicente Lucas e Hilário da Conceição. Deste grupo, apenas Coluna e Hilário integraram a equipa portuguesa que jogou no estádio Salazar naquilo que, na sua história, foi a primeira deslocação da selecção nacional "A" de Portugal ao então Ultramar. Na óptica dos organizadores, associar os brasileiros à cerimónia não só se procurou garantir antecipadamente o êxito no campo desportivo (dada a extraordinária categoria dos seus futebolistas), como também procurou dar ao acontecimento o simbolismo e a projecção que se impunham. Paralelamente ao trabalho desta comissão baseada em Lourenço Marques, havia uma outra que, formada por nomes sonantes da vida pública portuguesa, funcionava em Lisboa na resolução das muitas questões que a envergadura da organização exigia.
Três meses antes da data marcada para a inauguração, em Março de 1968, os CFM despacham para Lisboa uma importante delegação que, entre outras figuras, integrava o director dos serviços dos Portos, Caminhos de Ferro e Transportes de Moçambique, Eng. Fernando Seixas, e o Inspector superior da empresa, Eng. Francisco dos Santos Pinto Teixeira, com a missão de, pessoalmente, convidarem o presidente da República Portuguesa, Almirante Américo Tomás, o Presidente do Conselho (Chefe do .Governo), António de Oliveira Salazar, e o ministro do Ultramar, Silva Cunha, a assistirem à inauguração do estádio do CFVM. Entretanto, nenhuma das figuras convidadas compareceu, mas cada uma à sua maneira fez-se representar na cerimónia. Salazar enviou uma mensagem sonora que foi transmitida às mais de 50 mil pessoas pela instalação sonora no estádio e à uma significativa parte da restante população de Moçambique pelas antenas da rádio. Américo Tomás e Silva Cunha fizeram-se substituir pelos Subsecretários de Estado do Fomento Ultramarino e da Juventude e Desportos, respectivamente, Rui Patrício e Pinto Serrão.
Assistiram igualmente à cerimónia altos membros dos governos e das empresas dos Caminhos de Ferro e Transportes da África do Sul, do Malawi e da Swazilândia, para além de representações administrativas e desportivas dos restantes territórios africanos sob a administração portuguesa e de jornalistas de imprensa, rádio e televisão dos quatros cantos do Mundo. Aliás, foi o primeiro acontecimento desportivo ocorrido no chamado ultramar português de maior mediatização internacional e de maior mobilização humana e material. Na verdade, a 30 de Junho de 1968, a então cidade de Lourenço Marques foi a encruzilhada de todos os caminhos -de tódos os pontos de Moçambique, gente dos países vizinhos e de outros cantos da terra misturaram-se com os "Iaurentinos" na mais fantástica e impressionante aglutinação de cidadãos de diversas origens de que há memória em manifestações desportivas ocorridas na capital moçambicana. O grande ausente nos acontecimentos que assinalaram a inauguração do estádio Salazar foi o então Governador-geral de Moçambique, Baltazar Rebelo de Sousa, que na altura se encontrava em Lisboa onde, entretanto, não deixou de se deslocar ao local do estágio da selecção portuguesa para encorajar os seus jogadores ao mesmo tempo que os desejava uma boa estada em terras moçambicanas, assim como enviou um telegrama de felicitações e de encorajamento ao CFVM.
