Before establishing themselves in Victoria we know that the Augusitine Order in Gozo used to run a small church somewhere in the limits of Xaghra. This was dedicated to Il-Madonna tas-Seba' Ferhat, literally meaning Our Lady of the Seven Joys. A painting of St Augustine praying to Our Lady surrounded by seven angels (representing the seven joys) that is thought to date back since 802 still exists at the Victoria monastery. It is thought that this painting was brought from the Xaghra chapel.

We do not know much about the origins of the Victoria monastery itself but Augustine historians like Bonaventura Attardi and Wig Portelli say that it was already mentioned in the Order's registries of 1453. In October 1652 Pope Innocenzo X closed a number of monasteries including that in Gozo. However it was opened again after just four months thanks to the intervention of the Grand Master of the Order of St John Giovanni Paolo Lascaris Castellar who was very close to the monks. Today the monastery still boasts an antique portrait of Grand Master Lascaris. After more than 120 years since the first enlargement of the church, the Augustinians felt the need to rebuild this place of worship. Work started in 1662 and lasted four years. The church was consagrated by Bishop Mgr Labini on 12th May 1782. The monastery was also enlarged and work started in 1690. At first the Order decided to rebuild the monastery in stages but the earthquake of 1693 made the project a very urgent necessity. This was done according to the plans of Ferdinandu Valletta and was completed in 1717. The main altar piece of the church depicts St Augustine with St John the Baptist and Gulliermo of Aquitana. It was painted by the famous artist Mattia Preti in 1694 and was financed by Giovanni Gurgion. The figure of Our Lady on the main altar was brought over from Rome in 1765 Four large stone statues dominate the entrance to the church and monastery. They represent Our Lady Tac-Cintura, St Augustine, St Thomas of Villanova and St Nicholas of Tolentino. The statues were sculpted by Antonio Busuttil and were erected in front of the church in 1860.