L'ancienne cathédrale Saint-Gervais et saint-Protais de Lectoure date du 12e siècle. Fortement endommagée lors du siège de la ville par Louis XI en 1473, elle n'a conservé de cette époque que sa nef où se remarquent 6 impressionnantes piles contre les murs latéraux. Ces maçonneries qui forment les deux premières travées laissent penser que la nef était couverte de coupoles à l'image des églises d'Angoulême, Cahors ou Souillac, faisant de Lectoure l'exemple le plus méridional de ce type d'architecture si particulier en Midi-Pyrénées.
A la fin du 15e siècle, commence la reconstruction de l'église, d'abord par le clocher-donjon qui porte la date de 1488 et que l'on couronne d'une flèche s'élevant à 80 m. Les chapelles au nord de la nef sont réparées entre 1487 et 1495 par Mathieu Ragueneau, tailleur de pierre originaire de Tours. En outre, la reconstruction du clocher est terminée. On travaille aux chapelles sud de la nef jusque vers 1540.
Les guerres de religion mettent à sac l'église à peine achevée. C'est pourquoi une nouvelle campagne de travaux est engagée : les tribunes et la voûte de la nef sont terminées après 1638 par l'architecte Bathia, et, 15 ans plus tard, les consuls affirment que tout a été remis en ordre dans l'édifice.
Le choeur à déambulatoire est plus récent. A partir de 1743, sa construction est confiée à l'entrepreneur Isaïe Dansas aidé des maçons Bras et Garas. Il est une imitation tardive de celui des cathédrales voisines (Auch, Toulouse ou Agen) dont le modèle était venu du nord de la France au cours du 13e siècle.
La cathédrale devient église paroissiale après la Révolution française. La flèche du clocher, plusieurs fois foudroyée est détruite en 1782 puis le jubé en 1825.