Platsen där kyrkan står har förmodligen varit den centrala punkten i bygden sedan slutet av järnåldern. En stormansgård kan mycket väl ha legat på platsen och det som talar för det är de tre storhögar och en runhäll strax söder om kyrkan. Det är enligt olika källor inte helt otänkbart att Hilleshög uppfördes som gårdskyrka. Namnet Hilleshög kommer från den största gravhögen – Hilleshögen. Första gången platsen nämns i skrift är 1314 och då som Hildishög.
Hilleshögs kyrka byggdes någon gång mellan 1150-75 med absid, långhus, kor och torn i väster. Öppningen är på södra sidan. Kyrkan har än i dag den smala ingången som från början, innan vapenhuset byggdes, ledde direkt in från kyrkogården. På 1300-talet byggdes sakristian och vapenhuset på 1400-talet.
1692-93 byggdes bänkarna av Färentuna kyrkas klockare Herman Hansson. Bänkarna vitmålades senare, men under den stora renoveringen under 1920-talet togs den gamla färgen fram och bänkarna breddades.
På 1700-talet överkalkades kyrkans kalkmålningar och predikstol och läktare byggdes. Kyrkans första och hitintills enda orgel köps in. Kyrkklockorna flyttades från den separata klockstapeln som låg söder om kyrkan och fick sin nya boning uppe i tornet.
Kyrkan stängs
På en gemensam kyrkostämma den 31 oktober 1871 beslöt Färentuna och Hilleshögs församlingar om ”begagnande av Färentuna kyrka för båda församlingar gemensamt”. Beslutet fastställdes i skrivelse på Stockholms slott den 9 september 1873 och skrevs under av Oscar II.
Församlingsborna underhöll kyrkan i minsta möjliga mån och 1922 sattes en större renovering i gång under ledning av arkitekterna R S Enblom och K Nordenskjöld. Absidfönstret som togs fram på 1800-talet murades igen och den gamla gluggen togs fram. Golven läggs om och den fasta inredningen samt en del lösa inventarier konserveras. Träskulpturerna bärs ner från vinden och den fasta altarringen ersätts med en flyttbar kommunionsbänk. Konservator O Höök får uppdraget att knacka fram de gamla kalkmålningarna. 1928 får kyrkan elektrisk värmeledning i stället för de tidigare järnkaminerna. Samma år återinvigdes kyrkan som församlingskyrka av ärkebiskop Nathan Söderblom.
