A Igreja da Madalena que actualmente existe é o resultado de várias reconstruções da igreja que tinha sido construída em 1150 ou 1164, por ordem de D. Afonso Henriques junto à cerca moura.

Em 1363 um incêndio destruiu a igreja, tendo o rei D. Fernando I mandado reconstruí-la.

Em 1600 foi parcialmente destruída devido a um ciclone e em 1755 foi novamente deitada a baixo pelo Terremoto de 1755.

A rainha Dona Maria I em 1783 mandou reconstruir a igreja, novamente desde os seus alicerces. Posteriormente, em 1833 a igreja foi alvo de algumas alterações.

A Igreja da Madalena pertence à Irmandade do Senhor Jesus dos Perdões, Sta. Catarina e N. Sra. de Belém e tem no seu interior uma imagem do Cristo do Perdão, assim como pinturas de Pedro Alexandrino de Carvalho e esculturas de José de Almeida e Machado de Castro.

O Portal desta igreja, em estilo manuelino é considerado uma das obras a destacar desta época. Pensa-se que ele tenha vindo da Igreja da Conceição dos Freire, também destruída pelo terramoto. Neste portal, de arco trilobado, podem-se observar duas esferas armilares.

Proximidade pagã

Junto à Igreja da Madalena encontram-se quatro lápides romanas, por vezes chamadas de Lápides das Pedras Negras (por terem sido encontradas junto à rua com o mesmo nome), incorporadas na parede do edifífio na Travessa do Almada. Uma delas é um ex-voto à deusa Cibele e, segundo o olisipógrafo Augusto Vieira da Silva (1896-1951), foi encontrada com as outras três num conjunto de vestígios romanos descobertos em 1753 e 1754 quando se iniciaram trabalhos de construção no local. Entre os achados encontrar-se-iam também os restos de um edifício que alguns estudiosos crêem tratar-se das ruínas de um templo à deusa Cibele.

A Igreja da Madalena situa-se na freguesia da Madalena em Lisboa.

O Portal da Igreja foi classificado como Monumento Nacional pelo (Decreto 16-06-1910, DG 136, de 23-06-1910).