La première mention de la présence d'un orgue, construit par Jacques de Rasta, à la cathédrale Saint-André remonte à 1427. 

Un nouveau jubé, construit en 1531 sur les ordres de l'archevêque Charles de Granmont, a inspiré le commentaire suivant du chroniqueur anglais Andrew Boorde lorsque celui-ci visita Bordeaux en 1535 : « Dans la cathédrale Saint-André, se trouvent les plus belles et les plus grandes orgues de toute la chrétienté. »

En 1619, alors que le Cardinal François de Sourdis était l'évêque du lieu, le chapitre décida d'agrandir l'instrument. Cette restauration dura au-delà de onze ans et le résultat fut si désastreux que sept autres années furent nécessaires afin que l'instrument puisse être jouable. 

D'autres travaux furent régulièrement entrepris jusqu'en 1791 alors que - avec tout le mobilier de la cathédrale - l'orgue fut démonté et vendu dans la foulée de la Révolution française. Un édit du 15 décembre 1794 (25 frimaire an III) réquisitionna les tuyaux afin qu'ils soient fondus pour produire des boutons d'uniformes.

Lorsque le culte fut repris, suite au concordat de 1801, le jubé du 16e siècle était vide depuis dix ans. Comme l'église d'un village voisin, l'église Saint-Pierre de La Réole, était fermée, on décida, en avril 1804, de transférer l'orgue de cette église dans la cathédrale Saint-André. C'était un instrument construit en 1766 par le facteur toulousain Micot. Ces travaux ont été exécutés par Joseph Isnard et Simon Bayssac-Lebruyere. 

Toutefois, cet instrument s'avéra inadéquat pour la vaste cathédrale et il fut démonté en 1810 lorsque des réparations furent exécutées à la structure du jubé. Les marguilliers de Saint-André, considérant le problème du manque de majesté notoire de cet orgue, loin de tirer un enseignement de cette erreur, convoitaient à présent le plus bel instrument de Bordeaux, celui de l'église Sainte-Croix. C'est alors que l'archevêque fit appel à diverses personnalités musicales bordelaises pour obtenir leur appui dans cette cause. Celles-ci rédigèrent une pétition le 11 février 1811 en faveur de l'échange des orgues des deux édifices.

L'orgue de Dom François Bedos de Celles, construit en 1748, admirablement approprié à l'acoustique de Sainte-Croix, fut soumis qu'à de mineures modifications dans la seconde moitié du XVIIIe siècle. Un inventaire de 1756 indique que l'instrument possédait 44 jeux : Grand-Orgue 16 jeux, Positif 14, Récit 2 (cornet et trompette), Pédale 8, avec un jeu de Cromorne et un Cornet dans la division d'Écho.

Au terme d'un conflit arbitré par le ministre des Cultes, l'échange fut confirmé et encore, on fit appel à Joseph Isnard et Simon Bayssac-Lebruyere pour réaliser les travaux. L'orgue de Saint-André fut remonté en décembre 1812 à Sainte-Croix. Les buffets des deux instruments étaient toutefois demeurés à leur emplacement respectif. Si le remontage du Micot n'avait pas posé de problème particulier, il fallait agrandir le modeste buffet de la cathédrale afin qu'il puisse recevoir le matériel Dom Bedos. Le 12 avril 1812, on présenta un devis comprenant la construction de quatre nouvelles tourelles pour les Positif et Grand-Orgue avec diverses modifications, sculptures et peinture « acajour» du buffet, la réalisation de 68 tuyaux neuf pour regarnit la montre restée à Sainte-Croix, la construction d'une soufflerie et de porte-vents neufs, etc.

Toutefois plusieurs obstacles entravèrent la bonne marche des travaux: polémiques à propos de la nouvelle tribune de Combes achevée fin 1811, dont on doutait de la solidité mais surtout divers retards et erreurs administratifs dans le paiement des artisans. Malgré ces difficultés, l'orgue était enfin réceptionné le 27 mars 1817. Quelques modifications avait été apportées au devis initial, à la demande de l'organiste Ouelly qui visita le chantier: ajout d'un jeu de contre-bombarde au Pédalier, suppression de la grosse fourniture, pose d'un dessus de trompette en lieu et place du larigot du Positif, notamment. Les claviers furent en outre portés de 51 à 54 notes.

En général, l'effet de l'orgue de Dom Bedos fut désappointant une fois installé dans la cathédrale puisque celle-ci est huit à dix fois plus grande que l'église de Sainte-Croix. 

Une reconstruction fut réalisée entre 1837 et 1841 par le facteur Henry qui conçut les ailes convexes du buffet. 

En 1875-7, le facteur Wenner remplaça les deux jeux du Récit par une division complète de 14 jeux et remplaça l'action mécanique du Grand-Orgue ainsi que des notes basses du Récit par un traction pneumatique Barker.

Des travaux mineurs ont été effectués par Puget en 1921 et par Gloton, en 1933. 

En 1946, Robert Boisseau remplaça la traction mécanique de la pédale par une traction tubulaire pneumatique et, de 1954 à 1961, la traction des claviers a été complètement électrifiée par la firme Beuchet-Debierre.

En 1962, certains tuyaux datant de la restauration de Wenner (1875-7) s'écrasèrent dans la nef et, afin de prévenir tout autre affaissement, cette section de l'orgue a été reconstruite en utilisant des tuyaux peu attrayants de zinc électrolysés.
À ce moment, l'orgue contient 56 jeux : 26 de l'instrument original de Dom Bedos; 10 récupérés d'anciens instruments du 19e siècle, et 20 jeux modernes. Tel était l'instrument, capable de produire des sonorités inoubliables malgré son âge et la nature de sa composition, que le chanoine André Lacaze a présidé en tant qu'organiste titulaire jusqu'à sa mort en 1964. Il avait déjà soulevé la possibilité d'une restauration complète de l'instrument mais ce projet a été pris en charge par son successeur, Christian Robert qui avait l'appui de l'archevêque Mgr. Marius Maziers, le maire de Bordeaux, Jacques Chaban-Dalmas, et le ministre de la culture.

La principale question à résoudre était jusqu'où peut-on récupérer et préserver les jeux originaux de Dom Bedos. Sur avis d'André Marchal, de la Commission des Monuments Historiques, l'option de construire un nouvel instrument devait être privilégiée. Après des délais causés par les rénovations architecturales apportées à la cathédrale elle-même, les travaux de construction d'un nouvel orgue furent entrepris par la firme Gonzalez sous la direction de Émile Mothere, Francis Chapelet et Christian Robert.

Le nouvel instrument est inclus dans un buffet splendide conçu par les firmes Limouzin et Vernay dans le style que l'ancien buffet était avant 1875. 

L'instrument est complètement neuf à l'exception de quelques tuyaux de façade du Positif qui datent de 1934. L'orgue a été conçu en se basant sur l'information disponible concernant l'instrument original (1748) de Dom Bedos, sur le traité écrit par celui-ci « L'art du facteur d'orgue », sur l'instrument démonté en 1973, et sur les exigences du répertoire moderne.

Les facteurs ont voulu imiter certaines caractéristiques de l'orgue original de Dom Bedos : la flûte, le flageolet et le cornet du Positif; la doublette, mistures et la grande tierce du Grand-Orgue; le cornet de l'Écho, et la traction mécanique. Son traité, ci-devant mentionné, décrit un « Grand Jeu de Tierce de Pédale », lequel a été imité dans le nouvel orgue en construisant une division d'Écho qui soit expressive. Lorsque la boîte est fermée, cette division joue réellement son rôle d'écho mais lorsque elle est ouverte, l'accouplement de son Cornet à celui de la Pédale (Cornet 16') forme la Grande Tierce de Pédale préconisée par Dom Bedos. L'addition des jeux de Bourdon 16' et 32' à la Pédale ainsi que le maintien de la Flûte 4' au Positif se conforment aussi au traité.

Le nouveau Récit fut conçu pour refléter celui construit en 1875 par Georges Wenner avec l'addition d'une famille complète de Principaux (8'-4'-2') et une Mixture de 5 rangs, le tout de métal plus acceptable. Afin de permettre l'exécution du répertoire romantique et moderne, les claviers manuels ont été extensionnés à 61 notes et celui du pédalier, à 32 notes.

Georges Danion, de la firme Gonzalez, a dirigé les travaux de reconstruction. Jacques Bertrand a été responsable de l'harmonisation : son travail de reconciliation de l'accoustique de la cathédrale, les principaux de Dom Bedos et toutes les exigences de la part d'experts et d'organistes impliqués, mérite une admiration particulière. Le nouvel instrument a été inauguré, en 1982, par Jean-Jacques Grunenwald.

En 1987, un relevage a été confié à la maison Pesce de Pau par la Commission des Monuments Historiques sous le direction de Jean-Pierre Decavele. À cette occasion, un nouveau combinateur, conçu par Christian Robert, a été installé.

L'orgue a subit d'importants travaux de modernisation destinés à améliorer ses qualités sonores (notamment au pédalier), et le confort de l'organiste à la console. Ces travaux ont été réalisés par le facteur Marc Hédelin et inaugurés le 30 mai 2002 par l'organiste Guy Bovet.
Le buffet, provenant de La Réole et agrandi à plusieurs reprises, est classé « monument historique ».