A primeira Igreja ou Santuário construído em Natal e no RN foi a Capela do Forte, sob a invocação dos Três Reis Magos, que segundo os historiadores o início da construção data de 6 de janeiro de 1598. Até 1910, a celebração da Epifania, popularmente chamada Festa dos Reis Magos, fazia-se dentro da própria fortaleza, quando foi construída uma nova capela, no Morro da Limpa, próxima ao Forte, local onde foi celebrada até 1936. A primeira festa da atual capela, ou Santuário, do bairro de Santos Reis, realizou-se em janeiro de 1937.

As imagens dos três Reis Magos chegaram a Natal no ano de 1753, envidadas pelo então Rei de Portugal Dom José I, como presente de sua esposa Dna. Maria I a Capitania do Rio Grande, estas ficaram no Forte dos Reis Magos até o ano de 1910.

No dia 22 de agosto de 1964, foi criada por decreto de Dom Eugênio de Araújo Sales, a Paróquia de Santos Reis, passando de capela à Matriz. Após 18 anos como Paróquia, foi criada no dia 15 de abril de 1982, à Paróquia da Sagrada Família, elevando a Igreja da Limpa, à categoria de Santuário, chamando-se: Santuário Arquidiocesano dos Santos Reis.