Sucedeu a Bateria do Morro da Conceição, erguida pelo corsário francês René Duguay-Trouin quando da invasão da cidade do Rio de Janeiro (Setembro de 1711), dominando a enseada da Prainha e a Saúde (SOUZA, 1885:110).

Após essa invasão, foram aprimoradas algumas fortificações, construídas outras e iniciada uma muralha destinada à defesa da cidade pelo lado de terra. A Fortaleza da Conceição foi erguida nesse contexto, devido à necessidade de instalar canhões em um local alto o suficiente para varrer com a sua artilharia o trecho da orla marítima que se estende do Valongo à Praça Mauá (antigo cais do porto) e com alcance para a defesa da ilha das Enxadas
As obras para a sua construção iniciaram-se no segundo governo da Capitania do Rio de Janeiro de Antônio de Albuquerque Coelho de Carvalho (1711-1713), estando identificada sob a legenda "Q. Fortaleza da Conceição com suas comunicações ao mar e ao muro da cidade" (Planta da cidade de São Sebastião do Rio de Janeiro com suas fortificações, 1713. Arquivo Histórico Ultramarino, Lisboa), e no Plano de Defesa do porto e cidade do Rio de Janeiro, 1713 (Serviço Geográfico do Exército, Rio de Janeiro), ambos de autoria do Capitão de Engenheiros francês Jean Massé, que, após as invasões de corsários franceses em 1710 e em 1711, por determinação do rei D. João V (1705-1750), "em 1712 passou com o posto de brigadeiro ao Brasil para examinar e reparar as fortificações daquele Estado." (SOUZA VITERBO, 1988:154). Também está representada nas Plantas dos fortes de N. Sra. da Conceição e São Sebastião do Rio de Janeiro, c. 1714 (AHU, Lisboa) (IRIA, 1966:74).

A nova fortaleza ficou pronta em 1718. Orgulho da cidade, detinha a terceira maior artilharia do Rio de Janeiro, com "36 bocas de fogo e 1.000 balas de diferentes calibres", inferior apenas às das fortalezas de Santa Cruz e de São João, à entrada da barra da baía de Guanabara. Essa artilharia seria, entretanto, a sua condenação...

Erguida em terrenos da Mitra, vizinha ao Palácio do Bispo (atual Palácio Episcopal), à época da inauguração, afirmando que as obras haviam invadido uma parte dessas propriedades, explorando-se indevidamente uma pedreira ali existente para a sua construção, o bispo D. Francisco de São Jerônimo protestou, alegando que as salvas da nova fortificação, sob qualquer pretexto, abalavam as paredes da casa episcopal, perturbando-lhe os exercícios espirituais. Reclamava, assim, a título de indenização, uma lâmpada de prata para a Capela da Conceição no valor de cento e trinta mil-cruzados, importância considerável, à época.

Tendo-lhe sido dada razão pela Coroa, a Provisão do Conselho Ultramarino de 23 de dezembro de 1718, estipulava:

As obras foram complementadas no governo de Gomes Freire de Andrade, 1.º Conde de Bobadela (1733-1763). Data desse período a Planta da Fortaleza de Nossa Senhora da Conceição na cidade do Rio de Janeiro, 1730 (AHU, Lisboa) (IRIA, 1966:74), figurando como "Fortaleza da Conceição" na carta de André Vaz Figueira (Carta Topografica da Cidade de S. Sebastião do Rio de Janeiro, 1750. Mapoteca do Itamaraty, Rio de Janeiro), encomendada por Gomes Freire para mostrar as obras de seu governo.

No governo do Vice-rei D. Antônio Álvares da Cunha (1763-1767), foram levantadas a Casa das Armas, o Depósito de Equipamentos e Oficinas (SOUZA, 1885:110). Figura nesse período em um projeto anônimo, atribuído a José Custódio de Sá e Faria (Plano da Cidade do Rio de Janeiro Capital do Estado do Brazil, 1769. Mapoteca do Itamaraty, Rio de Janeiro). No governo do Vice-rei D. Luís de Almeida Portugal (1769-1779), e do Vice-rei D. José Luís de Castro (1790-1801), essas obras de defesa sofrem novos acréscimos (SOUZA, 1885:110).

No contexto da Devassa instaurada sobre a Inconfidência Mineira (1789-1792), à Fortaleza da Conceição foram recolhidos os seguintes conjurados:

Tomás Antônio Gonzaga (de 31 de agosto a 20 de setembro de 1791);
Domingos Vidal de Barbosa Laje (de 31 de agosto a 20 de outubro de 1791);
José Álvares Maciel (de 20 de setembro a 20 de outubro de 1791) (AQUINO et alii, 1998:94)
Posteriormente, aqui também estiveram detidos alguns integrantes da chamada Conjuração Baiana (1798).

Foi ainda nas oficinas de material bélico do forte que se registrou a primeira greve no Rio de Janeiro, em 1791, provocada pela falta de pagamento aos artífices, conforme comunicou à Metrópole o Vice-rei D. José Luís de Castro.