Malgré les recherches historiques menées par Renée Leulier dans le cadre d'une étude préalable à la restauration de l'église en 2015, les origines de l'église et de la paroisse restent floues. Un édifice préexiste certainement au Moyen Âge : des éléments de maçonnerie seraient conservés dans les parties basses de la nef.
Les visites pastorales fournissent des indications sur l'aspect de l'église aux 16e et 17e siècles. En 1578, lors des Guerres de religion, l'église est probablement dévastée. En 1603, le curé, Pierre de Crusiau, demande au cardinal de Sourdis de lui venir en aide pour réparer l’église et son mobilier. François de Sourdis exige alors, "sous peine d’interdiction de lad[ite] église", que cet édifice "en pauvre estat, ruinée et dénuée de tous ornemens et meubles requis au service divin et décoration" soit rapidement pourvu de tout ce qui était nécessaire au culte et que les réparations prévues soient effectuées (AD Gironde, G 666). Au début du 17e siècle, l’église est donc en ruines : les murs du cimetière sont éboulés, ceux de l’église en piètre état et la porte ne ferme plus. L’intérieur est dévasté : des autels brisés, un mobilier inexistant.
Trente ans plus tard, le curé Jean Deschamps réclame encore des réparations urgentes pour cette église "en un très piteux état" (AD Gironde G14). Le chanoine Pierre Frapereau, vicaire général de l’archevêché de Bordeaux, se rend alors à Saint-Estèphe et dresse, le 12 août 1646, un procès verbal de la visite : "dans la ditte esglise et au milieu de la nef d’icelle y a une grande eschelle qui traverse la ditte nef qui ser (sic) pour monter au clocher et sur l’esglise, et de chasque costé de la nef y a dou ayles appuyées par des gros pilliers, l’on vust qui servent et l’on autorise qui sont superflux, le tout aussy une grande difformité" (AD Gironde, G14 : procès verbal de visite de S[ain]t-Estèphe du 12/8/1646). En 1647, l’ordonnance rendue à la suite de cette visite mentionne le grand autel, les autels de Saint-Clément, de Saint-Sébastien et l’autel Dieu, un grand pilier de pierre qui est dans la nef et qui empêche la vue sur le grand autel, l’échelle qui est pour monter au clocher (AD Gironde, G14 : ordonnance sur la visite de l’église de Saint-Estèphe du 19/2/1647).
De la visite pastorale de 1659 (AD33, G 639, f° 151-152, 7/5/1659), on retient que seule l’abside est voûtée, le reste de l’édifice étant lambrissé, et que le bâtiment menace toujours ruine.
En 1735, la visite pastorale semble indiquer une église en bon état : des travaux y ont donc certainement été enfin réalisés (AD Gironde, G 649, État des réponses aux demandes qui seront faites aux articles que Monseigneur doit examiner dans la visite, 24/4/1735) : "l’église est bâttie de pierre, elle a de longueur soixante pieds, y compris les 2 ailes, trente-cinq de largeur, et vingt-quatre pieds de hauteur pour la nef et dix-huit pour chaque aile (…). Elle est lambrissée, le toit est en bon état. Elle est carlée. Les murailles sont bonnes et blanchies en dedans, garnie et recrépie par le dehors (…). Les fenêtres sont vitrées (…). Elles donnent asses de jour. Les portes sont en bon état avec serrure et verrouils. L’église est asses grande. L’église est au milieu du cimetière, ayant son autel au levant et la porte au couchant (…). Il y a un clocher quarré attenant au bas de l’église, il est bien couvert. Les murs en sont bons. L’escalier est assez bon et ferme à clef. Il y a deux cloches bénites (…)". Le décor intérieur est également décrit avec le maître-autel dédié à saint Etienne, orné d'un grand tableau représentant le martyr de saint Estienne, et un retable "peint et doré, sans aucune figure, orné de 4 colonnes d’ordre corinthien" (…). Deux chapelles sont situées de part et d'autre du grand autel, l’une dédiée à Notre Dame et l’autre à saint Clément. "Il n’y a ny voûte ny plafon. Les fenêtres sont asses grandes et donnent asses de jour, bien vitrées (…). Il y a des fonts baptismaux situés au bas de l’église, à côté de l’épître enclos d’une balustrade avec un tableau qui représente le baptême de Jésus Christ par s[ain]t Jean". La sacristie était établie derrière l’autel et deux arrières sacristies servaient "de décharge".
Selon R. Biron, c'est le curé Marc Antoine Lalanne, nommé en 1751 à Saint-Estèphe - fonction qu’il occupa jusqu’à sa mort en 1791 -, qui procéda à la reconstruction et à l'embellissement de l'église à partir de 1764. Dans le retable monumental est intégré un tableau réalisé par le peintre bordelais Pierre Lacour en 1772.
Des traces de ces travaux sont encore visibles dans les maçonneries, notamment le remaniement des fenêtres de la façade latérale sud dont l'appui a été remonté, pour répondre à l'aménagement de la galerie intérieure.
Vers 1784-1786, l'abbé Baurein indique : "Cette église, qui a été récemment embellie, est faite en forme de croix. Sa nef a cent huit pieds de longueur sur trente-six de largeur. Les deux chapelles qui en forment la croix, ont vingt pieds en quarré. L’Eglise, telle qu’elle étoit avant les embellissements qu’on y a faits, n’avoit rien de remarquable".
Au début du 19e siècle, la voûte autrefois en brique et en plâtre "façon de plafond" s'est écroulée. Un premier projet de reconstruction de la voûte est proposé en 1807-1810 par l'ingénieur ordinaire des Ponts et Chaussées du département M. Tannay. En 1811, c'est l'architecte Armand Corcelles qui propose devis, plan et cahier des charges : "la voûte de la grande nef de cette église sera de forme cintrée, construite au moyen de 29 fermes de bois de Dantzig et son intrados sera lambrissé en planches de la 1ère qualité de bois de nerva". L’architecte dresse le plan et la coupe de l’église, le 31 juillet 1816. Il est précisé que "la voûte sera peinte à trois couches à l'huile au blanc de céruse d'une couleur d'un ton clair de badigeon de pierre". Sont refaits aussi à cette occasion les "48m de balustrade en bois de nerva pour former le garde-fou des trois côtés des tribunes élevées dans la dite nef". Le chantier prend du retard, ce qui donne lieu à une correspondance régulière entre l'architecte et le préfet. On apprend ainsi que les fermes de la voûte ont été fabriquées et agencées dans "les magasins couverts de M. Hang, marchand de bois sur les glacis du château Trompette", puis transportées à Saint-Estèphe pour une mise en place à la fin de l'année 1816. Mais en juin 1817, l'ensemble des travaux, notamment l'installation de tous les éléments de menuiserie, n'est pas achevé.
Sur la vue du village publiée dans l'ouvrage de Gustave de Galard vers 1835, l'église apparaît dotée d'un clocher carré, percé d'une ouverture cintrée au premier étage mais ne présentant pas de flèche. Effectivement, la partie basse de la façade occidentale avec son fronton triangulaire et ses pilastres toscans date probablement des travaux menés par le curé Lalanne à partir de 1764.
En 1852, l'église est jugée trop petite et les habitants sont invités par l'archevêque de Bordeaux à la faire agrandir et à y élever un clocher.
En 1853, l'architecte Théodore-Henri Duphot propose un plan, un devis et un cahier des charges pour l'exhaussement du clocher. Des modifications y sont apportées suivant les recommandations de la Commission des Monuments historiques. Les plans sont finalement validés le 8 mai 1854 et les travaux confiés à l'entrepreneur Barbot. La construction en pierre de Bourg se déroula entre le 10 juillet et le 23 décembre 1854. Certaines modifications apportées par l'architecte furent contestées à l'issue des travaux : l'emploi de la pierre de Bourg qui a été préférée à celle de Saint-Savinien, certaines dimensions réduites, notamment la hauteur du dernier étage du clocher... La hauteur du clocher est de 35m 27 cm. En 1856, y est aménagé un beffroi pour l'installation des cloches.
En 1858, des plans et devis sont dressés par l'architecte Brun pour l'agrandissement de l'église ; est également prévue la construction d'un presbytère.
En 1861, un rapport de l'architecte Bonnore alerte sur les voûtes des chapelles qui exercent une pression trop lourde sur celles de l'abside ; il propose également d'agrandir l'église en construisant deux chapelles à l'ouest des deux actuelles "sans nuire au style général du bâtiment".
En 1862, deux possibilités d'agrandissement de l'église sont encore à l'étude : en allongeant et en reconstruisant le chœur plus en avant ou en construisant des bas-côtés. En 1866, ces projets de construction d'église et de presbytère sont toujours en attente.
En 1883, des travaux doivent être réalisés au dôme du clocher jugé peu solide ; l'architecte Bonnore propose en 1889 un devis pour réparer le clocher "qui menace de tomber" puis en 1891, un projet de construction d'une nouvelle église : ce dernier est rejeté.
La voûte peinte du chœur, les vitraux et la tribune d’orgue sont des ajouts du 19e siècle. A l’origine, la voûte et le vitrage étaient blancs pour mettre en valeur le retable polychrome qui était le point essentiel du décor. Certains vitraux, offerts par des familles locales, sont datés 1878 et portent la signature du peintre-verrier Dagrant.
En 1892, la construction d'une tribune d'orgues est validée par le conseil de fabrique et le conseil municipal.
En 1893, de nouveaux travaux doivent être effectués au clocher : "lorsque les cloches sont en mouvement, le clocher vacille". Jean Braquessac, entrepreneur de travaux publics à Saint-Christoly, est retenu pour la démolition puis la reconstruction du lanternon.
Avec son plan en croix latine à large nef unique, abside aveugle à trois pans et son décor baroque, l'église de Saint-Estèphe peut être comparée à celles de Saint-Joseph à Bordeaux, de Barsac ou de Cantenac.