Erguida pelos navegadores portugueses no século XIX (1838 – 1844), no então Morro da Ponta Negra, a estrutura serve como Base Naval do Namibe (BNN), desde 1991.

Remonta à primeira metade do século XIX, no contexto da colonização Portuguesa da baía do Namibe, com a função de defesa do presídio (estabelecimento militar de colonização) ali fundado.
Após os estudos da costa e dos sertões da região, iniciados em 1839, o então Governador-geral da Província de Angola, Manuel Eleutério Malheiro, determinou em Fevereiro de 1840 que se erguesse um forte na baía de Moçâmedes, época em que se iniciava a sua ocupação militar.
Essa fortificação foi concluída em 1844, recebendo oficialmente a designação de Forte de São Fernando pelo Ofício nº 249, de 12 de Junho de 1849, do Governador-geral ao Ministério do Ultramar em Lisboa. Era feita, dessa forma, uma homenagem a Fernando II de Portugal, esposo da rainha D. Maria II (1826-1828; 1834-1853).

Foi seu primeiro comandante o Tenente de Artilharia João Francisco Garcia (1840-1845). Os primeiros colonos civis de Moçâmedes foram dois grupos de Portugueses que se retiraram da Província de Pernambuco, no Brasil, quando da Revolta Praieira (1848-1850), em 1849.
No século XX, as suas dependências foram ocupadas pelo Comando Distrital da Polícia de Segurança Pública, até à independência do país.
Com a independência, em 11 de Novembro de 1975, o antigo Distrito de Moçâmedes passou a constituir a Província do Namibe.
A Fortaleza de Moçâmedes é um ponto de interesse histórico e turístico. Embora possa não estar em perfeitas condições devido ao desgaste do tempo, representa um marco importante da herança histórica e cultural de Angola.

O forte hoje em dia encontra-se ocupado pelo comando da Base Naval do Namibe, da Marinha de Angola.