O Hospital Naval de Natal (HNNa) teve sua origem no pavilhão de Enfermaria da antiga Escola de Aprendizes-Marinheiros do Rio Grande do Norte e compreendia uma área total de 715m².

Durante a Segunda Guerra Mundial, a cidade do Natal converteu-se, dada a sua situação geográfica, em um local de importância estratégica para a causa aliada, quando foi então criada a Comissão de Instalação da Base Naval de Natal, sob a direção do Contra-Almirante Ary Parreiras. Para o apoio logístico dessa nova estrutura, no setor de saúde, foi criado, em 4 de Fevereiro de 1944, o Hospital Naval de Natal. Seu primeiro Diretor foi o então CT (Md) Gerson de Sá Pinto Coutinho.

O efetivo militar na área de Natal crescia progressivamente pela criação de novas unidades: Centro de Instrução "Almirante Tamandaré", 3ª Companhia Regional de Fuzileiros Navais, Força Patrulha Costeira do Nordeste, etc.

Em 1947, começou a funcionar o serviço da Assistência Médica Social da Armada (AMSA) em Natal, quando o Hospital recebeu a visita, para a respectiva instalação, do seu então Diretor, o CC (Md) José da Cunha Soares Londres. Isto implicou em maior carga no setor de atendimento, que teve de sofrer ampliações, a fim de atender a maior demanda. Nesse ano foi construída mais uma enfermaria com capacidade para doze leitos e ampliando o laboratório de análises clínicas. Tinha o Hospital, na época, capacidade para trinta leitos. Em 13 de Fevereiro de 1953, o HNNa foi extinto, passando a categoria de Divisão de Saúde da Base Naval de Natal, na gestão do CT (Md) Cezar Luiz Bezerra Cavalcante. Em 11 de outubro de 1961, houve o restabelecimento do Hospital Naval de Natal, e teve como primeiro Diretor, o CC (Md) Fernando Paiva.

Com a extensão da AMSA em Natal, novas ampliações se tornaram necessárias para atendimento aos dependentes de militares, surgindo as seguintes instalações:

• 1962 – Pavilhão da maternidade;
• 1966 – Pavilhão da Seção de Odontologia;
• 1970 – 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; e
• 1976 – Paiol Médico Cirúrgico.

Em 13 de outubro de 1983, uma "Ala Nova" foi construída, onde presentemente funciona a Administração do Hospital e os ambulatórios. O Hospital Naval de Natal é um órgão técnico do Sistema de Saúde da Marinha e possui suas atividades e organizações regulamentadas pelo Comando de Operações Navais.