The original building of the current cathedral was built during the Spanish period. Just after the reconquest of the city to the Moors, the main mosque was decreed to be stripped of its Islamic past and consecrated as the parish church. However, under the rule of the Catholic Monarchs, the old building was demolished and a new church was erected, in Gothic style. The cathedral's small courtyard is the remnant of the larger Moorish court of the mosque. The Catholic Monarchs' coat of arms was placed in the courtyard where it can still be seen today. The cathedral extended to the opposite side of what is now Main Street.
The church of St. Mary the Crowned was the only Catholic church or institution that was not ransacked by the troops that took over the city in 1704. It was successfully protected by its staunch pastor, Juan Romero, his curate, and his bell-ringer. Thus, it is the only place where Catholic worship has taken place uninterruptedly from the definite Christian re-conquest of the town. Due to the building being severely damaged during the 1779–1783 Great Siege, in 1790 the then Governor of GibraltarSir Robert Boyd offered to rebuild the cathedral in return for part of the land on which the building originally stood in order to re-route Main Street. The route was re-modelled in 1801 so that Main Street could be straighter. The reconstruction took place in 1810 and the opportunity was also taken to widen Main Street. The clock tower was added in 1820 and in 1931 restoration work was carried out on the cathedral and the current west façade erected to replace the poorer one built in 1810. In 1881 the Church of St Mary's was the site of nearly fifty arrests as the Governor of Gibraltar sent police and reassigned soldiers to support Bishop Canilla as he attempted to enter his own church. A self-appointed "Committee of Elders" had said that they intended to take possession of the church and install their own "chief priest" against the will of the Governor and the Catholic church. Canilla was sent to his church on 2 March 1881 with police protection to install him in his church. When the new force came to the church they found it was occupied by 200 men and the police had to make four dozen arrests to establish order. Not only did Canilla now have possession of his church but he was also the owner as the governor arranged for the title deeds to be given to the new titular Bishop. Until the 19th century, anyone who died in Gibraltar had the right to be buried under the cathedral floor. Bishops are buried in a crypt beneath the statue of Our Lady of Europe. In 1943, Władysław Sikorski's coffin lay in state here, after his plane crashed into the sea just off Gibraltar.
