Wanneer de Romeinen uit deze streken zijn vertrokken en de lage landen bewoond worden door Franken en Friezen, trekt in de 8^e eeuw de prediker Werenfried hier naar toe. Hij zet zich in om deze bevolkingsgroepen tot het christendom te bekeren en doet dat onder meer in de omgeving van Elst. In Elst bouwt hij een eerste kerk op de fundamenten van die Romeinse tempels. Men maakt gebruik van nog aanwezig Romeins bouwmateriaal. Werenfried wordt na zijn dood bijgezet in de kerk in Elst.

De kerk wordt in de eeuwen erna flink vergroot en uitgebreid met een crypte. In de 10^e eeuw geeft de bisschop van Utrecht opdracht om daarin de relikwieën van de heilige Werenfried te plaatsen. Daarmee wordt Elst een pelgrimsoord.
Onder het koor van de huidige kerk bevindt zich een graf van een jonge vrouw, het Meisje van Elst. Haar kostbare stolpgraf ligt vlak tegen de zuidelijke buitenmuur van de laatste uitbreiding van de Romaanse kerk en dateert uit de 10^e eeuw.

In het begin van de 15^e eeuw ontstaan rigoureuze nieuwbouwplannen, die leiden tot de huidige gotische kerk. Als eerste wordt een sacristie aangebouwd, op en tegen de noordelijke muur van de Romaanse kerk. Die muur is geïntegreerd in het koor en daar nog zichtbaar. Boven de ingang tussen zuidportaal en schip brengt men het jaartal 1484 aan in Romeinse cijfers. Dit zou de voltooiing van het gotische kerkgebouw markeren, gewijd door de Rooms-Katholieke Kerk. In 1588 plunderen Spaanse soldaten de kerk en beroven haar van haar schatten.
Vanaf ongeveer 1600 wordt de kerk gebruikt door een protestantse gemeente (ook wel de Nederduits Gereformeerde Kerk genoemd). In 1701 slaat de bliksem in de torenspits, die brandend neerstort op het schip van de kerk. Toren en kerk branden grotendeels uit, waarbij ook de klokken verloren gaan. De protestantse gemeente moet de herstelwerkzaamheden zelf bekostigen. In 1703 wordt een nieuwe grote luidklok vervaardigd en opgehangen.

Tijdens de Tweede Wereldoorlog, in september 1944 bereikt de operatie Market Garden de Over-Betuwe. In en om Elst wordt dagenlang gevochten.
De toren van de Grote Kerk dient als Duitse waarnemingspost. Na heftige gevechten komt de kerk in handen van de geallieerden. Britse militairen zitten dan op de zwaar beschadigde toren en zijn doelwit voor de Duitsers.
Na dagen van beschietingen wordt de toren vol geraakt door Duits artillerievuur. De toren en de kerk staan in lichterlaaie. De volgende ochtend smeulen de houten delen nog; haan en klokkenstoel zijn naar beneden gevallen.
De luidklok uit 1703 is een paar jaar ervoor al naar beneden gehaald en verstopt. Deze heeft daardoor de oorlog overleefd.

Na een winter vol ontberingen en evacuatie, komen Elstenaren na mei 1945 terug in hun zwaar gehavende dorp.

Terwijl de wederopbouw van woonhuizen het belangrijkst is, denkt men ook na over de restauratie van de Grote Kerk.
In tussentijd neemt de Nederlands Hervormde Gemeente in oktober 1945 een houten noodkerk in gebruik, ter beschikking gesteld door de Zwitserse Reformierte Kirche.

Voordat de restauratie van het kerkgebouw begint, vraagt de Rijksdienst voor het Oudheidkundig Bodemonderzoek de Nederlands Hervormde Gemeente toestemming voor het doen van opgravingen. Men hoopt overblijfselen van Middeleeuwse kerken onder het verwoeste gebouw te vinden.
De opgravingen leveren indrukwekkende vondsten op.
Er komen inderdaad vroegmiddeleeuwse kerkmuren uit de 8^e eeuw te voorschijn. Maar iets dieper liggen zware funderingen. Dit is een onverwachte vondst. Het blijken overblijfselen van een Romeins bouwwerk, een Gallo-Romeinse tempel. Ook treft men restanten van een oudere Romeinse tempel aan.
Na de restauratie, waarbij de archeologische vondsten toegankelijk zijn gemaakt voor bezoekers, neemt de Hervormde Gemeente het gebouw in 1952 weer in gebruik. In de daaropvolgende jaren wordt de toren volledig hersteld.

De toren moet in de jaren ’90 van de vorige eeuw opnieuw gerestaureerd worden – nu met materialen die minder kwetsbaar zijn. Op het hoogste deel worden beelden van acht heiligen geplaatst, waaronder een beeld van Werenfried.

Het kerkgebouw inclusief de toren zijn eigendom van en worden gebruikt door de Protestantse Gemeente Elst.