Kirken er beliggende på en lille forhøjning nord for selve Randerup by, og beliggende omtrent midt i sognet. Kirken er fra middelalderen omkring år 1200. Randerup er salmedigteren Hans Adolph Brorsons ( 1694 - 1764) fødesogn, han blev født i præstegården, som dengang lå umiddelbart øst for kirken. Han far var præst ved kirken, som hans farfar også var det. Brorsons far døde i 1704, da H. A. Brorson var knap 10 år gammel. Brorsons mor giftede sig med børnenes huslærer, Oluf Holbek, som udnævntes til præst. Efter stedfaderens død i 1721 blev Hans Adolph Brorson præst i Randerup.
Kirken er i romansk stil, og bygningens ældste del - koret med triumfbuen - er bygget i rhinsk tufsten. Ellers består kirkeskibet af temmelig store granitkvadre, mens tårn og våbenhus er bygget overvejende med munkesten. Tårn og våbenhus regnes fra tiden op mod 1500-tallet.
I de første år af 2. verdenskrig gennemgik kirken en større restaurering, hvor både stole og gulv kom under behandling ligesom interiørets oprindelige farver søgtes genskabt.
Altertavlen, der er malet 1651, menes at være af Jens Olufsen, Varde. Vingerne er fornyet 1940 af P. Brodersen, Hjerpsted. Topstykkets flankerede figurer er Lukas og Johannes, mens de to andre evangelister sidder uden for topvingerne. Motivet er Jesu måltid med disciplene skærtorsdag aften, altså nadverens indstiftelse, og her kan man lægge mærke til den centrale placering Judasskikkelsen har. Judas er afbildet med ansigtet vendt bort fra Jesus, og hans ene fod ligner til forveksling en bukkefod, som symbol på det onde.
Kirkens alterkalk og disk er fra 1763 påtrykt mesterværket AG for københavnerguldsmeden Anders Jørgensen Graff.
Døbefonten er af granit og ligeså gammel som kirken. Der er to fremspringende menneskehoveder, og på soklens hjørner råt udhuggede menneskelige halvfigurer.
Krucifikset er højgotisk, fra første fjerdel af 1300-tallet og måler 73 cm i højden. Tornekronen og det meste af baghovedet samt en del fingre er fornyet. Det velbevarede kors, af hvilket halvdelen af øvre og hele nedre felt ligeledes er fornyet, er langs siderne tæt besat med store laurbærblade. Krucifikset reddedes 1928 i en miserabel tilstand af konservator Niels Termansen, der nystafferede det i 1940, da der ikke var bevaret oprindelige farver. Hænger i dag på kirkens nordvæg.
Prædikestol fra 1600-årene med fem fag reliefskårne scener af henholdsvis Jesu fødsel, dåben, Golgata med Maria og Johannes, opstandelsen og - oprindeligt med - retfærdighedens engel med sværd og vægtskål.
Ved udgangen til våbenhuset er der en indsamlingsbøsse, som hænger under et trætavle hvorpå der står:
Min Christen tag til Eftertanke / her lader Iesus Penge sance, / Leg efter Evne dit dertil, / I Dommer(n) Han betale vil.