Originalmente, a capela de Nossa Senhora da Conceição pertencia ao complexo da Fazenda Santa Cruz. Sua padroeira era Santa Bárbara, mas após a expulsão dos jesuítas e confisco da propriedade pela Coroa, a igreja da fazenda recebeu do vice-rei Marquês de Lavradio o título de Paróquia de Santa Cruz, sendo a padroeira alterada para Nossa Senhora da Conceição, utilizando ainda a matriz jesuítica. Apenas em 1896 foi erguida uma nova igreja no bairro de Santa Cruz, em região mais afastada daquela que trazia memórias imperiais, na Praça Dom Romualdo. No alto do morro estava a primeira igreja construída em consagração a Nossa Senhora da Conceição até 1971, quando fora demolida para dar espaço exclusivamente à Paróquia que vemos hoje.

No entanto, a igreja antiga e a paróquia nova conviveram juntas por algum tempo; tão logo a igreja nova começou a funcionar, a antiga foi sendo desmanchada. A paróquia, idealizada por padre Guilherme Decaminada, teve o início de sua construção em 1950, mas levou 24 anos para ser concluída. Construído o novo templo e derrubada a igreja histórica, a primeira missa na nova matriz foi celebrada em 1964. Possui uma arquitetura modernista e um projeto inovador e foi o maior pé-direito de um templo católico no Rio de Janeiro por muitos anos, perdendo esse posto quando a Catedral Metropolitana do Rio de Janeiro foi consagrada.