Holte Kirke er trods sin relativt unge alder hovedsageligt opført i middelalderlige stilformer.

Kirkens grundplan er romansk med tårnet vendt mod vest, derefter skib og korsarme og vendt mod øst koret med en halvrund apsis. 

Kirken har kamtakkede, blændingsprydede gavle og rødt tegltag og var oprindelig hvidkalket både ude og inde.

Inde har kirken fladt bjælkeloft i kor og skib, mens korsarmene har tøndehvælv og apsis kuppelhvælv. Vinduerne er nærmest rundbuede med blyindfattede glas i pastelfarver.

Kirken blev bygget i to etaper:

Første del bestående af kor og korsarme stod færdig i 1940. Anden del bestående af langskib og tårn stod færdig i 1944.  

Ideen til kirkebyggeriet opstod allerede kort efter år 1900, hvor man mente, at de 4.000 indbyggere i Holte Stationsby havde langt til kirken i Søllerød, - men først i 1928 nedsatte man en ’Komite til opførelse af en kirke i Søllerød Sogns vestlige del’. Der var forskellige forslag fremme vedrørende placeringen af kirken, deriblandt grunden hvor Rådhuset nu ligger.

Et halvt år efter Komiteens stiftelse købte man en egnet grund på den nordlige side af Toftevej, og man kontaktede arkitekt Frederik Kiørboe, som udarbejdede et forslag til en rundkirke på omkring 24 meters højde og med ca. 400 siddepladser. Men som årene gik, og mens de nødvendige økonomiske midler blev indsamlet, frafaldt man dog tanken om rundkirken, bl.a. fordi det blev klart, at der skulle bygges i flere etaper. Arkitekten tegnede så en kirke i mere traditionel landsbykirkestil. Denne plan blev godkendt i 1935. Imidlertid fik man i 1937 mulighed for at erhverve en bedre grund, nemlig den nuværende kirkegrund, som  er  en af sognets højest beliggende grunde. De to grunde blev mageskiftet.

I 1938 begyndte man kirkebyggeriets første etape, og den 26. juni fejrede man grundstensnedlæggelse. De tre grundsten er indmuret i fundamentet til det fritstående murede alter. Kirken blev indviet den 25. marts 1940. Det kostede 99.000 kr. at opføre første del af kirken. Pengene blev indsamlet af private ved basarer og lignende.

Tanken var, at sognet nu skulle klare sig med denne første del af kirken, indtil man fik indsamlet midler til at opføre langskib og tårn. Da Danmark i april 1940 blev besat af tyskerne, ønskede regeringen imidlertid at få gang i alt planlagt byggeri for at nedbringe arbejdsløsheden. Man frygtede ganske enkelt, at tyskerne ville sende danske arbejdsløse på tvangsarbejde i Tyskland. Staten bidrog derfor med 100.000 kr. og Søllerød Kommune med 15.000 kr. til færdiggørelsen af Holte Kirke, og man kunne således allerede i 1941 trods krigen – eller paradoksalt nok på grund af den – påbegynde opførelsen af langskib og tårn. Den færdige kirke blev indviet den 12. marts 1944.