Den ældste kirke i Hornslet var en trækirke fra 900-tallet. I 1100-tallet afløstes denne af en kampestensbygning, som stadig udgør den midterste del af den nuværende 39 m lange kirke.
Jørgen Rosenkrantz fra Rosenholm byggede til kirken og tilføjede bl.a. det 26 m høje tårn og kirkegårdsportalen med de indmurede nicher til hans og Dorte Langes våbenskjolde, som dog aldrig er blevet indsat.
Det tilbyggede våbenhus havde oprindelig kun én etage, men »Den Lærde Holger« (1596-1642), som også havde bygget »Pirkentavl« på Rosenholm, satte en etage mere på, som blev indrettet til håndbibliotek for egnens teologistuderende.
Kirken var ejet af Rosenkrantzerne indtil 1945.
Kirken blev herefter overdraget til menighedsrådet, men bærer tydeligt præg i sit indre af at have tilhørt denne slægt.
Forlængst gravsatte aner og forfædre fra andre hvilesteder er blevet bragt til et fælles hvilested i krypten under kirken, hvor der dog nu er ryddet op, og resterne er blevet begravet på Rosenkrantzernes gravsted ude på kirkegården.
Kirken er rigt udstyret med gravsten og epitafier over slægten Rosenkrantz, bl.a. over Erik Rosenkrantz med hans tre hustruer Margrethe Skeel, Mette Rosenkrantz og Margrethe Krabbe.
Under dette monument findes lænket til fodstykket i en tilpasset glasmontre en bog på 342 sider, som indeholder en ligtale over Erik Rosenkrantz, tillige med en levnedsbeskrivelse og nogle latinske og danske vers. Sidekoret er Jørgen Rosenkrantz eget kapel og er bygget af ham selv.
På gulvet ligger hans gravsten, den sidste over slægten Rosenkrantz. Altertavlen er en gotisk fløjaltertavle skåret af billedskærer Claus Berg fra Odense. Degnestolen hører til kirkens fornemste inventar og er udført af den hollandske billedskærer Mikkel van Groningen, som har udført mange fornemme arbejder, heriblandt prædikestolen i Århus Domkirke.
Orglet er skænket af lensbaron Hans Rosenkrantz i 1899. Orglet er et Høhneorgel, også en sjældenhed, da der kun findes få af dette mærke i hele Norden.
Kirkerummet har skiftet udseende ved forskellige restaureringer i årenes løb. I 1960 erstattedes kirkebænkene af løse stole, og den barokke alterskranke blev erstattet af en mere funkis præget.
Samme år blev døbefonten flyttet ned midt i kirken under det store kalkmaleri, som blev fremdraget i forbindelse med restaureringen. Billedet er fra omkring 1250 og har vakt meget stor opmærksomhed, idet der ikke andre steder her i landet findes noget tilsvarende. Det gengiver scener fra datidens populære ridder-krøniker fra kong Arthurs hof. Hovedtemaet er jagten på den hellige gral, og i nederste frise udkæmpes et drabeligt ridderslag.
Ved den sidste restaurering i 1988 blev stolene udskiftet med nye kirkebænke og den barokke alterskranke, som havde været opbevaret på loftet på Rosenholm, blev atter sat op. Ligeledes kom døbefonten atter på sin plads i koret. Den er hugget af stenmester Horder.
Hornslet Kirke knejser på en bakketop i den sydlige bydel og er omgivet af et velholdt anlæg og kirkegård. I anlægget ved kapellet står frihedsmonumentet over byens 5 faldne frihedskæmpere i krigen 1940-1945.