En meget omtalt mordbrand er årsagen til, at den nuværende store Randlev Præstgegård ved Odder blev opført. Den forrige gik op i luer i 1749 - en interessant begivenhed, der er skildret i "En jydsk Mordbrænderhistorie" af forfatteren Steen Steensen Blicher og i "Det gyselige Mordbrænderie" af hans far, Niels Blicher, der var præst ved kirken 1794-1823. Forfatteren selv fungerede som præstegårdsforpagter i sine unge dage i årene 1811-19.
De store og flotte præstegårde er typisk for egnen omkring Aarhus og Skanderborg. Stuehuset i Randlev er som et par andre præstegårds-stuehuse i nabolaget på 27 fag. Det er opført i bindingsværk med hvidtede tavl og svært sorttjæret træværk. Huset havde oprindelig traditionelt stråtag, der i 1900-tallet blev erstattet af røde vingetegl. I samme forbindelse blev et par af avlslængerne nedrevet efter frasalg af præstegårdsjorden.
Resten af bygningerne blev reddet; stuehuset blev restaureret i 1923 og den sidste avlsbygning i 1990. De omkranser nu den vidtstrakte gårdsplads sammen med den lille romanske granitkirke uden tårn og kirkegården, og udgør som i tidligere tider en smuk helhed for sognets menighedsarbejde.