Ved Randrup kirkeruin ses fundamentresterne og grundplanen af en kirke eller et kapel fra middelalderen omkring 1200-tallet. Der findes desværre næsten ingen oplysninger om kirkens opførelse, funktion eller nedrivning. Nationalmuseet har dog tidligere gennemført en mindre undersøgelse af stedet.
Efter den korte gåtur ad stien fra den nuværende asfaltvej nord for ruinen, ses ruinen i en indhegnet græsgang lige vest for gården. I den ca. 15 m. lange, 7,5 m. brede og øst - vest orienterede kirkeruin ses kirkens skib og det lige afsluttede kor mod øst tydeligt.
Udenfor koret er der tilføjet en mindre firkantet bygning, og hele bygningen og kirkegården udenfor omsluttes af et dige som stadig ses - særligt nord og vest for ruinen.
Bygningen var opført i natursten lagt i kalkmørtel og murenes inderside var beklædt med hvide limkalksten. Bygningsmaterialerne er givetvis blevet genbrugt efter nedrivningen. Fra Randrupgård stammer således en indmuret kvadersten med et indhugget skaktern-mønster. Stenen ligger nu på Randers Museum, men kan også genfindes i nutidens kirker i området ved Falslev, Svenstrup og Spentrup.
I guidebogen ”Mariageregnens arkæologiske minder” forklarer K.M. Christensen stenens evt. betydning:
”De er foreslået tolket som stenmesternes fritidssyssel, stenskadeudbedring eller regnebræt, mystisk-symbolske talkombinationer eller meddelelser og endeligt tolket som symbolet på hvidt/sort, godt/ondt og liv/død. Populært kaldes stenene for ”Fandens spillebræt”, hvor man kommer til at tænke på menneskers spil med Døden om tidspunktet for at forlade denne verden. Sagn beretter også om, at Djævelen ofte generede kirkebyggeriet ved at rive det ned om natten, hvad der var bygget op om dagen. Bygmesteren kunne så lave et skakbræt til Djævelen, der i sin spillelidenskab ville blive så optaget, at byggeriet kunne fortsættes uforstyrret”
Hvorfor og hvornår nedrivningen fandt sted vides ikke. Kirken optræder i al fald ikke på Videnskabernes Selskabs kort fra 1791. Årsagen kan være den store befolkningsnedgang efter middelalderens pestepidemier og/eller sognesammenlægningerne efter reformationen i 1536.
Alene i de 4 herreder syd for Mariager Fjord kendes til i alt 36 ødekirker, hvoraf de 24 har kunne stedfæstes. Kirkerne har skullet fungere samtidig med de 42 sognekirker der er i området, så det var måske ikke så mærkeligt, at der i senmiddelalderen og efter reformationen blev ”luget ud” i antallet af kirker. På markerne ved Kjellerupgård kun ca. 2,5 km. nordøst for Randrup findes resterne af en tilsvarende nedrevet kirke. (se Svenstrup runesten).