L'actuel édifice succède à une ancienne église située « hors-les-murs », c'est-à-dire en dehors des remparts de la ville. La construction de la troisième enceinte urbaine, incluant l'antique sanctuaire, contribue au développement du quartier dans le courant du XIV siècle. Ce dernier est alors le domaine des marchands et artisans, tels que « carpenteyres » (charpentiers) ou « fustiers » (tonneliers).
Le chantier de la nouvelle église est confié par le roi Louis XI à l'architecte Jean Lebas, originaire de Saintes. En 1466, un collège de chanoines est installé dans l'église, toujours en construction. Cette dernière devient une étape importante sur le chemin de Saint-Jacques-de-Compostelle, ce dont témoigne notamment la chapelle Saint-Jacques. Confréries et corporations contribuent par des donations à l'avancement des travaux, lesquels ne sont pourtant pas achevés avant le XVI siècle.
L'édifice souffre des conséquences du tremblement de terre qui frappe Bordeaux le 10 août 1759. Frappée à plusieurs reprises par la foudre, faute de paratonnerre, la flèche du campanile est emportée par un ouragan en septembre 1768. Un projet de restauration avait été réalisé en 1755 qui demeura sans suite. En janvier 1769, la fabrique de l'église décide de confier la restauration de son campanile à l'architecte du roi, Jacques Hardouin-Mansart de Sagonne (1711-1778), dernier des Mansart et petit-fils de Jules Hardouin-Mansart, venu à Bordeaux dans l'espoir de se voir confier la réalisation du nouvel hôtel de ville.Daté du 21 janvier 1769, ce projet n'eut guère plus de succès que le précédent, faute de fonds suffisants pour sa réalisation et ce, malgré la quête décidée en avril 1771 par la fabrique auprès des fidèles. Sa construction était en effet estimée à 50 000 livres. Le projet de Mansart de Sagonne est définitivement écarté lorsqu'en 1811, la paroisse adopte le projet de l'architecte Louis Combes. La reconstruction de la flèche attendra cependant 1860, date à laquelle Paul Abadie, architecte du Sacré-Coeur à Paris, entame les travaux dans le style gothique de l'édifice. Ils seront achevés en 1869.
Le clocher présentait jusqu'alors un aspect tronqué. Au début du XIX siècle, il accueille le télégraphe Chappe. Lors de son passage à Bordeaux en 1843, Victor Hugo le décrit en ces termes : La tour, quoique couronnée encore d'un bloc à huit pans et à huit pignons, est fruste et tronquée à son sommet. On sent qu'elle est décapitée et morte. Le vent et le jour passent à travers ses longues ogives sans fenestrages et sans meneaux comme à travers de grands ossements. Ce n'est plus un clocher ; c'est le squelette d'un clocher »
En 1791, le directoire du département ordonne la suppression de l'ancien cimetière paroissial entourant l'église, l'actuelle place Meynard. Les ossements sont entassés dans la crypte située sous le clocher, puis recouverts de terre. C'est au cours de ces travaux que sont découverts plusieurs dizaines de corps momifiés, les « momies de Saint-Michel ». Ces dernières sont placées dans la crypte, laquelle est ouverte à la visite jusqu'en 1979. À cette date, les corps sont de nouveau inhumés, cette fois au cimetière de la Chartreuse.
Le 1 avril 1903, un bref apostolique fait de l'église paroissiale Saint-Michel une basilique mineure.
Le 21 juin 1940, des bombardement soufflent une partie des vitraux de la basilique, lesquels sont remplacés après le conflit par de verrières modernistes dus à l'artiste Max Ingrand.
