Den nuværende Bregnet Kirke stammer fra anden halvdel af 1400-tallet. Den har erstattet en romansk kirke, sandsynligvis opført i granitkvadre. Ligesom mange andre af landets romanske kirker, er denne sikkert opført i 1100-tallet. Om der også før den tid har været en kirke på stedet er slet ikke usandsynligt. I Ringelmoseskoven øst for kirken findes en gammel helligkilde, der i kristen tid er opkaldt efter Tobias fra det apokryfe skrift Tobits Bog. Man har fremført en teori om, at den ældste Bregnet Kirke er opført som valfartskirke i forbindelse med kilden. Fra den romanske kirke er i dag bevaret to genstande. Den ene er kirkens døbefont, som er omtalt herunder. Den anden var kirkeklokken, der var støbt i 1100-tallet og dermed er en af de ældste i landet. Den revnede imidlertid i 1898, men blev af arkitekt F. Uldall skænket til Nationalmuseet, hvor den stadig befinder sig.  Den nuværende kirke I midten af 1400-tallet opstod der et ønske om at forny kirken. Om de har været egentlige saglige grunde til at nedrive den gamle bygning, eller det blot var ønsket om at skabe noget nyt og større ved man ikke. Men for bygherren var det ikke usædvanligt at udskifte ældre kirkebygninger. Det var nemlig Otte Nielsen Rosenkrantz, der på samme tid fornyede kirkerne i Tirstrup og Marie Magdalene. Men i modsætning til disse to er Bregnet Kirke ikke opført med ham som personlig ejer, men derimod i hans egenskab som kongelig lensmand på Kalø Slot. Kirken har Århus Stift-bispen Jens Iversen Langes våbenskjold malet som kalkmaleri på korets sydlige hvælving, hvorfor den uden tvivl er indviet i hans tid som biskop. Kirkebygningen er opført gotisk stil og består af skib og kor ud i ét. Koret har en tresidet afslutning mod øst. Mod vest et kirketårn, der oprindeligt var et styltetårn med en åbning på vestsiden, som er tilmuret senere. Mod syd findes våbenhuset. Både tårn og våbenhus har kamtakkede gavle. Materialet er røde munkesten, men kirken fremstår hvidkalket. Man har tidligere været af den opfattelse, at hele bygningen er opført på samme tid. I dag mener man, at tårn og våbenhus sandsynlig er tilføjelser fra 1500-tallet. Skib og kor er dog meget velbevarede. Norddøren er muret til, men ses tydeligt som en niche i ydermuren. Man bemærker endvidere, at kirken kun har sydvendte vinduer. I det indre har kirken oprindelige spidsbuede hvælvinger.  Restaureringen 1872 I 1872 gennemgik Bregnet Kirke en hård og ret uheldig restaurering ved bygningsinspektør Walther, der få år senere også gav rundkirken i nabosognet Thorsager en hård medfart. Han forsøgte om at omskabe den gotiske kirkebygning til den romanske stil. Alt inventaret bortset fra døbefonten og alterstagerne blev kasseret. Der indbyggedes nye hvælvpiller og nye gjordbuer i romansk stil, således at det gotiske præg blev sløret. Der blev fremstillet nyt inventar; nye stolestader, prædikestol, knæfald, altertavle, samt høje brystningspaneler langs væggene. Resultatet var ikke heldigt. Kirkerummet fremstod rodet og usammenhængende.  Restaureringen 2006 Efter mange års tilløb og forhandlinger med myndighederne kunne man i 2006 indlede en restaurering af kirken, der på mange måder handlede om at fjerne misforståelserne fra 1800-tallet. Walthers hvælvpiller og gjordbuer blev fjernet, så rummet atter fik sin oprindelige smukke geometri tilbage. Gulvene blev enten fornyede eller omlagte. Vinduerne i korets østvæg blev blændet af. Vægpanelerne blev fjernet. Et forslag om at kassere stolestaderne og prædikestolen fra 1872 blev ikke gennemført. Disse blev i stedet malede i helt nye farver. En nyt alterbord er opmuret, og her står en ny altertavle, et trefløjet nadverbillede malet af Arne Haugen Sørensen. Samme kunstner har desuden forestået de øvrige udsmykningsopgaver i forbindelse med restaureringen. Som kirkerummet fremtræder i sin nye form, er det i høj grad moderne. Men opformningen har i høj grad også fremhævet rummets smukke gotiske proportioner.