De oudste vermelding van Doorn dateert waarschijnlijk van kort na 838. Maar in de eeuw daarvoor stond er mogelijk al een houten kerkje. Sporen hiervan zijn bij opgravingen niet terug gevonden. Voor 946 wordt Doorn al genoemd met de toevoeging dat er een kerk staat. Ten noorden van de kerk zijn meer dan 130 (delen van) skeletten aangetroffen, waarvan de oudste door middel van koolstofdatering, ook wel C14-datering genoemd, gedateerd kon worden tussen 880 en 987 na Chr. * 
De Doornse kerk is een van de oudste van het Utrechtse platteland. Uit deze kerk zijn de kerken van Leersum, Cothen, Langbroek en mogelijk ook van Amerongen ontstaan.
De ouderdom van de kerk blijkt onder meer uit de tufstenen noordmuur. Tufsteen is de steensoort die vooraf ging aan de zogenaamde kloostermoppen. In deze oudste muur bevindt zich ook het Noormannenpoortje, dat de oorspronkelijke ingang van de kerk bevat, die waarschijnlijk al in de 14e eeuw is dichtgemetseld. Verder zijn er in deze muur twee hagioscopen te vinden. Door deze vensters (nu al eeuwen dichtgemetseld) konden geëxcommuniceerden of besmettelijke zieken toch de dienst bijwonen.

Men gaat er vanuit, gezien de bouwstijl, dat er in de 12e eeuw een Romaans schip is gebouwd op de plaats van of naast het oorspronkelijke houten kerkje. Waarschijnlijk is in de 14e eeuw de toren hieraan gebouwd. Deze is letterlijk tegen de kerk aan gebouwd: de toren heeft maar drie zijden. In de toren hangt de huidige luidklok die uit 1720 stamt. Op de klok was de volgende tekst aangebracht SI DEUS PRO NOBIS QUIS CONTRA NOS oftewel: zo God voor ons is wie zal tegen ons zijn De Romaanse kerk is in de tweede helft van de 15e eeuw in Gotische vormen vergroot aan de zuidzijde door toevoeging van een overwelfde sacristie met steunberen. Niet lang daarna is de Romaanse koorsluiting gedeeltelijk gesloopt en het koor verlengd en verhoogd in baksteen. In 1924 is aan de zuidzijde nog een extra beuk geplaatst. Sinds die tijd is de kerk niet meer in omvang veranderd.In de jaren 1985-1996 werd het kerkgebouw ingrijpend gerestaureerd en gerenoveerd Zo werd ook een glazen corridor tussen de kerk en het kerkelijk centrum de Koningshof gerealiseerd. In 1989 werd, ter gelegenheid van het elfhonderdjarig bestaan van Doorn een carillon in de toren aangebracht.
In 1996 heeft in de toren beperkt archeologisch onderzoek plaatsgevonden. Aanleiding tot dit onderzoek was de vondst onder de vloer van de toren van enkele stukken beeldhouwwerk. Het bleek te gaan om fragmenten van zes beschilderde reliëfs met religieuze voorstellingen, waaronder de Judaskus en Veronica met de zweetdoek. Deze reliëfs dateren uit circa 1525. Vrij zeker zijn ze na de Reformatie hergebruikt als torenvloer. De stukken zijn waarschijnlijk afkomstig van een doxaal dat heeft gestaan tussen koor en schip, ter afscheiding van het geestelijke en wereldlijke deel van de kerk. * 

In 2011 is het interieur van de kerk aangepast aan de vernieuwde inzichten rond de liturgische vormgevingen die de Protestantse Gemeente in zijn vieringen wil gebruiken. Bij de aanpassing van het interieur is gekozen voor een verbinding tussen de monumentale waarden van het historische gebouw en de ruimte en inrichting die nodig is voor de zondagse vieringen.

De Maartenskerk is gebouwd op de west/oost-as en kent drie 'delen', van west naar oost: toren, schip en koor. Het westen is in de Bijbelse en liturgische beeldtaal de plaats van de zonsondergang, de einden van de aarde, en het oosten is de plaats van de opgang van de Zon der gerechtigheid en de opstanding van Christus. Deze oriëntatie en haar betekenis geeft richting aan de liturgie en de kerkinrichting. Zo is de westzijde de kerk de nieuwe plaats geworden van de Doop. Het schip met de zijbeuk is het "plein" waar de gemeente zich verzamelt. Het koor is oorspronkelijk bedoeld als ruimte voor de viering van het Heilig Avondmaal. Bij de laatste verbouwing is ook de Stiltekapel ingericht.