Durante o contexto da chamada União das Coroas Ibéricas (1580-1640), no qual Portugal ficou subordinado à Espanha, as Cartas Régias do rei Felipe II, soberano que então dominava as duas nações, determinaram ao governador-geral do Estado do Brasil, Dom Francisco de Souza, a concreta ocupação da Capitania. Coube a Manuel Mascarenhas Homem e Feliciano Coelho de Carvalho, capitães mores, respectivamente, de Pernambuco e Paraíba, comandarem a empreitada cujos objetivos eram: retomar o controle das terras, ameaçado pela incômoda presença francesa, e fundar uma cidade. Foi a partir de tais determinações que, a 6 de janeiro de 1598, teve início a construção da Fortaleza dos Reis Magos.

A construção da Fortaleza, após a realização de acordos de paz que possibilitaram o relativo apaziguamento dos nativos, tornou-se de fundamental importância para a conquista e ocupação da região Norte da outrora colônia lusitana na América (CASCUDO, 1999). Símbolo da colonização portuguesa em nosso litoral, a Fortaleza dos Reis Magos teve sua planta concebida pelo padre jesuíta Gaspar de Samperes, sob as influências da arquitetura italiana que, no século XVI, era considerada a mais avançada concepção arquitetônica direcionada para o uso militar (MEDEIROS FILHO, 1997).

De 1633 a 1654, durante o domínio holandês sobre a Capitania do Rio Grande, foram alterados os topônimos da cidade, modificado para Nova Amsterdã, e da Fortaleza dos Reis Magos, símbolo da conquista portuguesa nos trópicos. “Em vez de Santos Reis, aclamam o Castelo de Ceulen [ou Keulen]” (CASCUDO, 1999, p.65), A denominação era “uma homenagem ao General Mathias Von Keulen, alto conselheiro da Companhia das Índias Ocidentais e que fizera parte da expedição vitoriosa” (NESI, 1994). Tais mudanças, entretanto, foram efêmeras. Quando os holandeses foram expulsos do Brasil, as tradicionais denominações lusitanas são retomadas.

Na segunda década do século XVII, a fortificação recebeu aditamentos, responsáveis por sua configuração atual, sob a direção de Francisco de Frias de Mesquita, à época, engenheiro-mor do Estado do Brasil (MEDEIROS FILHO, 1997). Em Capítulos de História Colonial Capistrano de Abreu, um dos ícones da historiografia nacional, registra a importância da Fortaleza ao afirmar que “à sua sombra medrou o que é hoje a cidade de Natal” (ABREU, 1998, p. 70). Não obstante, a formação da cidade ocorreu a alguns quilômetros da Fortaleza. Nesse sentido, existe relativo consenso na historiografia norte-rio-grandense acerca de que a região elevada onde atualmente encontra-se a Praça André de Albuquerque, no centro do bairro Cidade Alta, corresponde ao núcleo do sítio histórico de Natal (CASCUDO, 1999).

A Fortaleza dos Reis Magos abriga em seu interior, desde 1976, o chamado Marco de Touros, o mais antigo padrão de posse chantado na antiga colônia portuguesa. Sua origem em território potiguar remonta a 1501, quando aportou no litoral a esquadra responsável pelo “primeiro episódio histórico ocorrido” na outrora Capitania do Rio Grande (MEDEIROS FILHO, 1997).
Tombada pela antiga SPHAN (Secretaria do Patrimônio Artístico Nacional), antecessora do atual IPHAN (Instituto do Patrimônio Histórico e Artístico Nacional), a “fortificação representa o mais expressivo marco histórico do Rio Grande do Norte, e um dos mais importantes monumentos nacionais” (NESI, 1994)

A Fortaleza da Barra do Rio Grande, popularmente conhecida como Forte dos Reis Magos ou Fortaleza dos Reis Magos, foi o marco inicial da cidade —Recebeu esse nome em função da data de início da sua construção, 6 de janeiro de 1598, Dia de Reis, pelo calendário católico.