Bryrup Kirke lå i sine første 700 år næsten alene nede i dalen side om side med Bryrup, som var en nydannet gård, et såkaldt torp, oprettet på udmarken til sognets gamle by, Velling. Oprettelsen af gården og bygningen af kirken skete i sidste halvdel af 1100-tallet, hvor mange stenkirker blev bygget i Danmark.
Kirkebygningen stammer fra romansk tid, men der er ikke mange romanske træk tilbage. Skibets mure er omkring 120 cm tykke og opført af marksten, iblandet jernal og murstensstore kvadre af frådsten. Koret var langt i forhold til det oprindelige skib, som imidlertid forlængedes med et overhvælvet fag som led i større ombygninger, der foregik fra slutningen af 1400-talet og frem til reformationen. Forlængelsen i vestenden er bygget i munkesten og har muligvis været tænkt som basis for et tårn. Men ligesom pastoratets andre kirker forblev Bryrup Kirke "kullet", altså uden tårn. I ombygningsperioden indbyggedes krydshvælv med halvstensribber i koret og kvartstensribber i skibet, hvor langmurene forhøjedes med et par skifter, og korgavlen fik sine stræbepiller. Korbuen (triumfbuen) ombyggedes til en spidsbue, og som sidste led i den store ombygning kom våbenhuset til . Af de oprindelige vinduer kan kun spores to. Det ene er i skibets nordvæg; det andet i korets østvæg, hvor det nu indvendigt fremstår som en niche.
Komforten har ikke været stor i de gamle kirker. Først i 1895 opstilledes en kakkelovn, der en halv snes år senere udskiftedes med en større. Der kom elektricitet i 1926, og ved en restaurering i 1970 etableredes det første oliefyrede varmluftanlæg. Kirkens tag havde i mange år været tegl, men i 1967 blev kirken atter blytækket, som den havde været det tilbage i tiden. Ved kirkens fortsatte restaurering i 1971 fornyedes gulvet, og kirken fik nyt stoleværk, så der blev ca. 100 siddepladser. Arbejdet udførtes af snedkermester Christensen fra Brædstrup, og træværket maledes af den lokale malermester, Frode Jensen. Orgelet fra 1928/29 blev i 1974 erstattet af et nyt fra Bruno Christensen & Sønner. Orgelet er tegnet af arkitekt Preben Thorsen, som var arkitekt ved hele restaureringen.
Spor af senmiddelalderlige kalkmalerier var allerede fundet i 1903, men først i 1990 blev kalkmalerierne afdækket. De ældste tegninger fra 1200-tallet på skibets nordvæg blev atter overkalket. Dekorationen i korets hvælv er samtidig med hvælvenes opførelse i slutningen af 1400-tallet. Hvælvene i skibet er udført og dekoreret af "Liljemesteren", som desuden udsmykkede Vinding Kirke. "Liljemesteren" var en murermester fra Ribe, hvis folk i perioden 1500-1520 rejste rundt i den sydlige og midterste del af Jylland og moderniserede kirker ved at bygge tårne, opsætte hvælv og samtidig dekorere hvælvene. Fra samme periode stammer et kalkmalet fantasidyr omkring et spygat i skibets midterfag.
Gennem årene kneb det ofte med kirkernes vedligeholdelse, og helt galt stod det til, da landet i 1659 var hærget af såvel de svenske fjender som af brandenborgere og polakker, der var vores allierede, men selv måtte skaffe føden. I 1661 indberettede Pastor Povl Nielsen Brandt, at alle pastoratets kirker var meget forfaldne. I Bryrup Kirke var der hverken vinduer eller døre, og prædikestolen manglede, men kirken syntes dog at kunne stå af sig selv i modsætning til kirkerne i Vrads og Vinding, der ville falde, om de ikke fik hjælp. I Bryrup fandtes kun et rødt fløjlsmessehagel, kalk og disk af sølv, to messinglysestager foruden et gammelt egeskab til messeklæderne og en lille klokke uden knebel.
Den gamle prædikestol var nok alligevel ikke så langt væk, for den restaureredes i 1661. Også det middelalderlige alterbord af pudsede og kalkede granitkvadre med et panel i eg fra omkring år 1600 og den romanske døbefont med løveornamenter overlevede. Der var dog intet dåbsfad, og sådan et fik man først omkring 1930. En dåbskande i tin anskaffedes i 1862 men blev erstattet af en ny i 1952. Altertavlen er fremstillet i 1841 i senklassicistisk stil af en selvlært, lokal snedker, som genbrugte ældre dele. Alterbilledet er fra 1841 og forestiller Kristus på korset. Det gamle sæt kalk og disk omstøbtes i 1730 til et nyt sæt med tilsætning af mere sølv, mens alterstagerne fra 1500-tallet stadig findes. En skibsmodel skænket kirken i december 1945.Kirkeklokken, der nu er ophængt på skibets vestgavl, omstøbtes i 1759 i København. For at kirkeklokken skulle kunne høres længere omkring, ophængtes imidlertid i 1998 en ny klokke støbt i Holland i en nykonstrueret, blytækket klokkestabel nord for kirken. Pastoratets præst, Provst Jens Lidegaard, forfattede en inskription til klokken: "Jeg kalder over by og skov - og ringer til vor Herres lov".
Bryrup Kirke og Bryrupgård kom formentlig under Voer Kloster, som efter reformationen i 1536 blev krongods. Gård og kirke var stadig knyttet til hinanden, idet Bryrupgård som anneksgård bidrog til husførelsen for præsten i Vinding-Bryrup-Vrads Pastorat. Gård og kirke var underlagt Skanderborg Slot indtil 1767, hvor Skanderborg rytterdistrikts ejendomme solgtes på auktion. Kirkerne privatiseredes ved at køberne købte retten til kirketiende og dermed fik pligten til at holde kirken ved lige. Perioden med privateje varede 46 år, og kirken havde overvejende lokale ejere. Blandt ejerne skal især nævnes møller på Nørre Mølle, nu Katrinedal, Caspar Lohmann, som i 1774 købte både Vinding og Bryrup Kirke. Caspar Lohmann nåede at bo i alle pastoratets sogne, inden han mæt af dage døde på Fuglsang i Vinding i 1804. Længe inden havde han solgt de to kirker til Christian Høegh fra Horsens, som omkring 1790 solgte tienden i anparterne til sognets gårdmænd. Bryrup Kirke forblev i sognebørnenes eje, indtil den overgik tilselveje i 1913.
Kirkegården er omgivet af et stendige, hvoraf nordsidens vestlige del er flere hundrede år gammelt. Kirkegårdsmuren blev bygget omkring år 1900, mens stendigerne mod øst og vest er opført omkring 1960.