Holms kyrka uppfördes 1678, som sockenkyrka i Holms församling och slottskyrka till Sjöö slott beläget bortom kyrkan. Namnet Holm kommer troligen av holme, och syftar på att området länge var en ö i Mälaren. Kristendomen kom tidigt till denna lilla ö, vilket framgår av en runsten utanför kyrkan. Att det fanns en kyrka i Holm 1209 är känt genom brev till församlingen från dåvarande ärkebiskopen. Rester av denna kyrka återfinns i murarna idag, men inget föremål från den medeltida kyrkan finns bevarat. Enligt traditionen ska den medeltida kyrkan ha förstörts av en brand.
Närheten till Sjöö slott har spelat en stor roll i Holms kyrkas historia. Ägaren till Sjöö slott var länge kyrkans patronus. Första gången Sjöö nämns i böckerna var 1409 och det finns tydliga förteckningar över de olika ätter som stått som ägare. Från 1600-talet är Sjöö slott i ätten Stenbocks ägo, och det är Johan Gabriel Stenbock som på 1670-talet uppför slottet som det ser ut idag, och som även 1678 låter bygga om (eller upp, om kyrkan eventuellt förstörts av brand) Holms kyrka.
Sjöö slott ritades av Tessin d.ä. Om stilen sägs det att Tessin "förenade romersk barock med sval nordisk klassicism". Under samma period och slottsbygget till kom också Holms kyrka. Den som ledde byggnationen av Sjöö slott var Mattias Spihler och när Johan Gabriel Stenbock valde att bygga upp eller bygga om den medeltida församlingskyrkan i stället för att skapa en särskild slottskyrka gick även det uppdraget till Spihler.
Intressant är att altaret och predikstolen ritades av den kände Burchart Precht, som bland mycket annan kyrkokonst skapat Uppsala domkyrkas predikstol. Tyvärr brann Holms kyrka redan 1723 och då förstördes både predikstol och altaruppsats.
Magnus Gabriel de la Gardie som då blivit ägare till Sjöö slott låter återuppbygga kyrkan, som åter är i bruk vid en ärkebiskopsvisitation 1735. Man försöker att exteriört i stor utsträckning återuppbygga kyrkan som före branden. Interiören byggs däremot om, och får tydlig karaktär av 1700-tal. Kyrkan får en s.k. altarpredikstol där predikstolen är placerad över altaret för att markera ordets och predikans betydelse i gudstjänsten. Nybyggnation av altarpredikstolar förbjöds i slutet av 1800-talet och de är relativt ovanliga, även om det finns ytterligare en altarpredikstol i Lagunda församling, i Fröslunda kyrka. Ännu mera ovanligt är att man vid införskaffandet av en orgel till kyrkan år 1752 lät placera orgeln över altarpredikstolen. Ett fåtal exempel finns på detta på andra håll, bland annat i Röros kyrka i Norge. Orgelfasaden dekorerades med donatorernas adelsvapen. Tyvärr är orgeln idag helt obrukbar.
År 1822 var oturen åter framme och kyrkan träffades av ett blixtnedslag. Troligen slog blixten ned i det centraltorn där klockorna hängde. Detta hade redan återuppbyggts efter den tidigare branden 1723 men nu förstördes det helt liksom kyrkans tak. Efter detta byggdes taket som det ser ut idag, och klockorna flyttades till en klockstapel väster om kyrkan.
Holm och Kulla var ett pastorat med Holm som huvudkyrka, från medeltid fram till 1878. Därefter ingick församlingen i Hjälstaholms pastorat. Vissa förändringar gjordes i kyrkan, och bland annat invigdes en ny orgel år 1889. Folkmängden i församlingen minskade snabbt vilket gjorde att kyrkan nyttjades allt mindre. Holms kyrka kom därför att stå öde under vissa delar av 1900-talet och förföll. Bland annat nyttjades den som spannmålsmagasin.
1950 kunde kyrkan återinvigas efter restaurering. Fram till 2010 då Lagunda församling bildades av dåvarande Gryta pastorat med 10 församlingar, var Holm Sveriges minsta församling med 20-25 invånare.