Randrup optræder første gang i kildematerialet i 1396. Fra 1512 til 1637 tilhørte gården adelsslægten Seefeld.
Enevold Jensen Seefeld opførte omkring 1550 den nuværende vestfløj i bindingsværk, der på nordvestsiden fortsat står i sortbejdset svært egetømmer. Mod gårdsiden i øst blev fløjen ombygget omkring 1570 af Jacob Enevoldsen Seefeld, hvilket førte til et mere præsentabelt renæssanceanlæg med et rundt trappetårn i to etager.
Omkring år 1700 blev østsiden ommuret, og på hver side af tårnet blev føjet to korte udløberfløje med svejfede barokgavle. Til vestfløjen blev i 1858 føjet en noget større sydfløj, kaldet den italienske fløj. Fløjen i villastil er prydet med plaquetter efter Bertel Thorvaldsen: Natten og Dagen og de tre årstider. Endelig blev hele anlægget udbygget i årene 1865-69, dels med den såkaldte mejerifløj i nord, dels med en forlængelse af sydfløjen i form af en køkkenafdeling.
Randrup tilhører i dag familien Hjorth, som har ejet stedet siden 1924. Til gården hører godt 400 ha.
