The sanctuary originated as a natural cave which was consecrated as a church at an unknown date, and local traditions link its establishment to antiquity or the medieval period.

The present building was constructed in various stages between the late 16th and 18th centuries, incorporating parts of the natural cave in which the church originated.

A number of notable people visited the sanctuary over the centuries, including several kings and viceroys of Sicily, some Hospitaller Grand Masters and Pope John Paul II.

According to tradition, the cave was originally a place of worship for the nymph Calypso, but it became a Christian site after St Paul's shipwreck on Malta in 60 AD.

[4] Bishop Miguel Juan Balaguer Camarasa reported that a Turk who had damaged the fresco with a knife later became sick but was miraculously healed after praying for forgiveness, and he sent candles to the sanctuary as a form of gratitude.

Grand Master Alof de Wignacourt is said to have visited the church on a regular basis after the attack, and devotion to the sanctuary subsequently increased.

[8] The entrance to the sanctuary complex is through a Baroque monumental archway which bears the date 1719 and which contains an inscription in Latin and archaic Maltese.

The main entrance leads to a sacristy, which allows access to a tunnel lined with ex-voto offerings and a rock-hewn crypt which was excavated in the 16th century.

The artwork is believed to actually date back to around the late 12th or early 13th centuries, and its style is inspired from Byzantine art with Sicilian influences and a vernacular quality.

The church contains a number of other artworks by Giuseppe Calleja, Anton Falzon, Pietru Pawl Caruana and possibly Stefano Erardi, along with some paintings made by unknown artists.

[2][9] A notable example is a painting depicting a Venetian ship and an icon of the Virgin Mary and Jesus which might have originated from the Kykkos Monastery in Cyprus.

Relics of St Vincent were also given to the sanctuary later on by Dun Lawrenz Grech Delicata, after he had acquired them through Pope Pius VII from the Catacomb of Priscilla in Rome on 21 April 1820.

[2] On 6 October 1999, MaltaPost issued a postage stamp and a miniature sheet to commemorate the centenary of the crowning of Our Lady of Mellieħa.