L'edifici original de l'actual catedral va ser construïda sota la sobirania espanyola. Poc després de la conquesta de la ciutat als musulmans, la mesquita principal va ser consagrada amb el nom de Santa Maria la Coronada y San Bernardo[1]). Malgrat això, sota el regnat dels Reis Catòlics, l'antic edifici va ser demolit i es va construir una nova església d'estil gòtic. Al pati de la catedral, romanent del període musulmà, encara s'hi conserva l'escut d'armes dels Reis Catòlics.
L'església va ser l'únic edifici catòlic que no va ser saquejat per les tropes britàniques quan van prendre Gibraltar el 1704. Va ser protegida amb èxit pel seu cura Juan Romero.[2] Així, és l'únic lloc d'adoració on els catòlics han pogut assistir ininterrompudament des de la reconquesta cristiana de la ciutat.
Com que l'edifici va ser seriosament malmès durant el setge de 1779 a 1783, el 1790 l'aleshores Governador de Gibraltar Sir Robert Boyd va oferir reconstruir la catedral a canvi de part del terreny on s'assentava l'edifici per millorar el traçat de Main Street. La reconstrucció va tenir lloc el 1810 i es va aprofitar per ampliar el carrer. El rellotge de torre va ser afegit el 1820 i el 1931 es va restaurar la catedral, reemplaçant l'anterior façana de 1810 per l'actual.[3]
Fins al segle xix, qualsevol persona que morís a Gibraltar tenia el dret a ser enterrat sota la catedral. Els bisbes estan enterrats en una cripta sota l'estàtua de la Mare de Déu d'Europa.[3]
↑Jackson, William. The Rock of the Gibraltarians. A History of Gibraltar. 2a edició. Grendon, Northamptonshire, UK: Gibraltar Books, 1990, p. 99–101. ISBN 0-948466-14-6.