Følgende beskrivelse af Koldmose Kirke og dens historie baserer sig på sognepræst John Kristensens skrift i forbindelse med kirkens 100-års jubilæum i 2010, ”Koldmose Kirke i 100 år”.

4. søndag i advent 1910 blev Koldmose Kirke indviet ved en festgudstjeneste. Den fattige, østlige ende af Lerup-Tranum Sognekald havde nu endelig fået sin egen kirke, hvor det før gjaldt, at de havde ti kilometer eller mere til Tranum Kirke. Lovgivningen gjorde det dengang muligt at sætte et kirkebyggeri på finansloven, hvis det kunne godtgøres, at det for befolkningen på en hel egn gjaldt, at man havde over en vis afstand til den nærmeste kirke.
Vejen frem til nedlæggelsen af grundstenen 19. maj 1910 og indvielsen senere samme år er lang og fuld af mange forhindringer. Allerede i 1898 opkom tanken om opførelsen af kirken, men uenighed om bl.a. den rette placering af kirken gjorde, at der skulle gå en del år, inden kirken endelig stod klar til brug.

Bygningen
Manden bag Koldmose Kirkes bygning er arkitekt Vilhelm Ahlmann, der bl.a. tegnede den nærliggende Vedsted Kirke, som blev indviet i 1899. Han blev da også i første omgang bedt om at tegne en kirkebygning med forbillede i netop den, men det viste sig at være begrænset, hvad der kunne fås for de 18.500, som var afsat til byggeriet. Derfor må Ahlmann lave nye tegninger, hvorved bl.a. et tårn udelukkes; det skaber stor skuffelse i lokalbefolkningen. Resultatet bliver den særegne bygning, som man nu ser – en på samme tid enkel og himmelstræbende helligdom med aner til norske stavkirker og nybyggerkirker på den amerikanske prærie. Kirkerummet er smukt og harmonisk, og det ses, at arkitekten har leget med både lys og dimensioner inden for de muligheder og rammer, som romansk unggotik giver.
Til erstatning for det ellers ønskede tårn opsattes det spinkle, kobbertækte spir eller tagrytter.
Kirken er opført af gule teglsten, brændte af ler fra lokalområdet.

Altertavle og døbefont
Den første alterudsmykning er det krucifiks, som i dag ses hænge på kirkens nordvæg. I begyndelsen af 1950’erne opstilledes nemlig den nuværende altertavle, som er et relief i en hvid, grønlandsk marmor og udført af billedhuggeren Aksel Hansen i årene 1903-11. Det er udlånt på ubestemt tid af Ny Carlsberg Glyptoteket og beskriver situationen, hvor Jesus velsigner de små børn. Det er i sandhed et klenodie og uhyre detaljeret; man kan stadig blive ved med at opdage noget, som man ikke har set før. Relieffet gør Koldmose Kirke til en udpræget dåbskirke, og helheden ville have været endnu bedre, hvis den forholdsvis lille granitdøbefont, som der i øvrigt ikke findes noget materiale om, var blevet ved med at stå midt for alteret, som det oprindeligt var arkitektens ønske.

Orgel
Frem til 1916 var der intet orgel i Koldmose Kirke, men dette år døde en unge mand fra Koldmose af tuberkulose. Han efterlod sig 1.800 kr., der bekoster indkøbet af et stort harmonium.
Først i 1981 får kirken sit første rigtige orgel, skænket af den kendte kirkekunstner og guldsmed Bent Exner, der i en årrække har haft det stående hjemme hos sig selv på den nærliggende Røde Hede. Orglet, der er bygget i 1903 af Busch og Sønner og oprindeligt har stået i Lemming Kirke ved Silkeborg, har fire stemmer og opsættes på kirkens pulpitur, netop som det fra begyndelsen har været arkitekt Ahlmanns idé.
Omkring årtusindskiftet står det imidlertid klart, at orglet ikke kan reddes fra et omsiggribende ormeangreb, og det erstattes af det nuværende instrument, som oprindeligt har stået i Sengeløse Kirke på Sjælland, og som placeres i nede i kirkens skib, da det er for højt til at stå på pulpituret.

Kirkegård

Selve grunden, hvorpå Koldmose Kirke er bygger, var fra begyndelsen en stor udfordring i forhold til at få en kirkegård på stedet. Derfor gik der en del år, inden en sådan kunne tages i brug; i 1928 skred lokalbefolkningen til handling og kørte i løbet af kort tid 3.500 læs tørvemuld på grunden. Den nu færdige kirkegård blev dog ikke taget i brug straks, for de fleste havde familiegravsted i Tranum, og således skulle man frem til 1936, inden den første blev begravet på Koldmose Kirkegård - en ung mand, der var omkommet ved en færdselsulykke i Halvrimmen. 

Hvor mange af de lokale beboere i begyndelse var lidt skuffede over den kirkebygning, som de gerne havde set større, gælder det i dag, at kirken for rigtigt mange er kommet til at stå som et symbol på deres barndom og ungdom, for de fleste forlod området, men når de så besøger deres hjemegn, så må de en tur omkring Koldmose Kirke. Desuden glæder rigtigt mange turister sig over at lægge vejen forbi den helt særegne og smukke bygning – og ikke mindst over at betragte det smukke alterrelief.