De St.Gudulakerk is genoemd naar de heilige Gudula. Zij werd in 652 geboren uit een adellijk Frankisch geslacht afkomstig uit het tegenwoordige Belgisch Henegouwen.?Haar oorspronkelijke naam is Goedele. De St. Michielskathedraal te Brussel werd enige tijd naar haar vernoemd. Het is onduidelijk, waarom de kerk in Lochem als enige in de Graafschap en de Achterhoek haar naam draagt. Wel is opmerkelijk dat de stad Rhede (bisdom M?nster) een Sankt Gudula Kirche kent.
De bouwgeschiedenis gaat terug naar omstreeks 950 toen een houten schuurkerkje werd gebouwd met een lengte van 12 m en een breedte van 4 m. De paalgaten van enige houten stijlen zijn op regelmatige afstand in het middenschip aangetroffen. Het houten kerkje is omstreeks het jaar 1000 vervangen door een eenbeukig stenen gebouwtje met een halfrond gesloten koor, beide gefundeerd op veldkeien.
Omstreeks 1100 werd het eenbeukige schip vervangen door een driebeukig turfstenen schip, waarvan de zijbeuken aan de oostzijde mogelijk halfrond gesloten waren. Ca. tweehonderd jaar later werd de kerk verbouwd tot een kruiskerk met een gothisch koor. Omstreeks 1550 werden de zijbeuken verbreed en verlengd en na meerdere werkzaamheden tijdens de afgelopen decennia ontstond de huidige hallenkerk.
Met de bouw van de toren werd in 1478 begonnen. De toren kan regelmatig worden beklommen.
Tijdens de jongste restauratie van de kerk in 1973-1976 zijn beeltenissen van Sint Christoffel met het kind en de Heilige Sebastianus en Jacobus Maior weer zorgvuldig onder de deklaag vandaan gehaald. Bovendien vond men naast deze schilderingen aan weerszijden van het venster nog een kleine boom van Jesse. Voorts zijn later meerdere schilderingen onder deklagen tevoorschijn gekomen.
In 1903 schonk de leerfabrikant G. Naeff de gemeente Lochem een carillon. De beiaard in de toren wordt elke woensdag tijdens de markt te Lochem bespeeld.?De Gudulakerk heeft een zeer goede akoestiek, waardoor musici en koren van naam graag in deze kerk optreden.