Historians assume that the church was probably built during the late 11th century, after Roger I of Sicily arrived in Malta and reconquered the island from the Moors.

It is said that the church was built as a thanksgiving by the Christians for the liberation of Malta from Muslim rule.

In 1409, Blanche I of Navarre assigned the church under the care of Canon Ruġġieru Segona.

Originally this church had one altar and a painting depicting the Virgin Mary with baby Jesus.

Two other side altars were added sometime later, one dedicated to St Angelo, patron of the fort, while the other to Saint Barbara.