L'église primitive est fondée au III^e siècle.

Reconstruite au cours du 11ᵉ siècle, la cathédrale est consacrée en 1096.

En 1305, Bertrand de Got, archevêque de Bordeaux accède au trône de Saint Pierre sous le nom de Clément V (le fameux Pape Clément).

Ce dernier ne parvient pas à enraciner son influence à Rome, et décide d'installer le siège de la papauté en France, à Avignon. 

Il n'oublie cependant pas ses origines gasconnes et libère des fonds importants pour l'extension et l'embellissement de la cathédrale.

Sous son action, l'ancienne cathédrale romane prend l'aspect d'un édifice gothique, style architectural en pleine expansion partout en France

Jusqu’au XVIII^e siècle, la cathédrale est totalement englobée dans un réseau de ruelles étroites bordées de constructions anciennes.

En 1836, les autorités municipales installent la mairie dans l’ancienne résidence de l’archevêque (palais Rohan, construit en 1770).

Elles décident de concentrer autour de l'hôtel de ville plusieurs édifices publics (caserne, facultés, hôpital...), et de moderniser le tissu urbain.

En 1844, malgré les protestations de la commission des Monuments historiques, la municipalité décide la destruction de l'ancien cloître situé sur le flanc sud.

L'architecte Paul Abadie qui prend la tête du chantier en 1863, fait détruire en 1865 le cloître et élève à sa place, en 1869-1879, des sacristies et des annexes.