Origem
O Hospital Naval de Natal (HNNa) originou-se do pavilhão de Enfermaria da antiga Escola de Aprendizes-Marinheiros do Rio Grande do Norte, que compreendia uma área total de 715m².

Enfermaria da Escola de Aprendizes Marinheiros do Rio Grande do Norte (1908-1942)
Durante a Segunda Guerra Mundial, a cidade de Natal tornou-se, devido à sua posição geográfica privilegiada, um ponto de importância estratégica para a causa aliada. Nesse contexto, foi criada a Comissão de Instalação da Base Naval de Natal, sob a direção do Contra-Almirante Ary Parreiras.
Para prover o apoio logístico na área de saúde dessa nova estrutura, foi criado, em 4 de fevereiro de 1944, o Hospital Naval de Natal. Seu primeiro Diretor foi o então Capitão-Tenente (Médico) Gerson de Sá Pinto Coutinho.
O efetivo militar na região de Natal crescia progressivamente com a criação de novas unidades, entre elas: Centro de Instrução "Almirante Tamandaré", 3ª Companhia Regional de Fuzileiros Navais e Força de Patrulha Costeira do Nordeste.
Expansão e Desenvolvimento
Em 1947, iniciou-se o funcionamento do serviço da Assistência Médica Social da Armada (AMSA) em Natal.
O Hospital recebeu, para a respectiva instalação, a visita de seu então Diretor, o Capitão de Corveta (Médico) José da Cunha Soares Londres. Essa implantação resultou em maior demanda no setor de atendimento, exigindo ampliações nas instalações. Nesse mesmo ano, foi construída uma nova enfermaria com capacidade para doze leitos e ampliado o laboratório de análises clínicas. À época, o Hospital contava com capacidade total de trinta leitos.
Em 13 de fevereiro de 1953, o HNNa foi extinto, sendo rebaixado à categoria de Divisão de Saúde da Base Naval de Natal, durante a gestão do Capitão-Tenente (Médico) Cezar Luiz Bezerra Cavalcante. Em 11 de outubro de 1961, houve o restabelecimento do Hospital Naval de Natal, tendo como primeiro Diretor o Capitão de Corveta (Médico) Fernando Paiva.
Com a ampliação da AMSA em Natal, novas expansões tornaram-se necessárias para o atendimento aos dependentes de militares, resultando nas seguintes instalações:
- 1962 – Pavilhão da Maternidade
- 1966 – Pavilhão da Seção de Odontologia
- 1967 – Consultórios
- 1971 – Farmácia e Junta Regional de Saúde
- 1972 – Sala de Estado, Secretaria do FUSMA e Alojamento de Praças
- 1973 – Centro Cirúrgico e Praça D'Armas
- 1976 – Paiol Médico-Cirúrgico
Em 13 de outubro de 1983, foi construída uma "Ala Nova", onde atualmente funcionam a Administração do Hospital e os ambulatórios.



