Villestrup adskiller sig fra de fleste danske herregårde ved ikke at have middelalderlige rødder. Godset er opstået af en såkaldt enestegård i kølvandet på borgerkrigen Grevens Fejde. Lensmand på Aalborghus Axel Juul arvede denne gård i 1535, og inden længe var nabolandsbyen Villestrup nedlagt, muligvis som følge af, at bønderne blev fradømt deres gårde for deltagelse i Skipper Clements jyske oprør. I 1538 påbegyndte Juul opførelsen af et massivt anlæg på en holm i en opstemmet sø. Det firfløjede bygningsværk var fuldendt i 1542, og på det tidspunkt var Villestrup ikke kun et af landets første renæssanceanlæg, men også et af tidens største herregårdsbyggerier prydet med tårne og tinder, porte og kamtakkede gavle. Sydfløjen var oprindelig i tre stokværk, mens de tre øvrige fløje var i to etager, og nordfløjen udstyret med et kraftigt porttårn.
Byggeriets afslutning blev fejret med bryllup mellem Axel Juul og Kirsten Lunge. En bevaret indvielsestavle over den nordvendte port beretter om begivenhederne. Ti år senere lod parret sig portrættere med hver sine våben på to sandstensrelieffer. De sad oprindelig i nordfløjens nu nedrevne porttårn, men flankerer i dag sydfløjens barokportal.
Sandstensportalen fra 1630’erne skyldes sandsynligvis billedhugger Henrik Henriksen.
Axel Juuls efterkommere ejede Villestrup i næsten 200 år til 1725. Under den sidste ejer af slægten, Frederik Ovesen Juul, påbegyndtes anlæggelsen af en have nord for hovedbygningen.
I 1755 kom Villestrup i Rosenkrantzslægtens besiddelse, og i 1757 blev den ophøjet til et baroni. I de følgende år blev hovedbygningens indre omskabt i rokokostil, samtidig med at haveanlægget fra 1690’erne blev udbygget til et barokanlæg, hvoraf betydelige dele er bevaret. Det samme gælder ladegårdsanlægget fra 1785.
Det relativt store barokanlæg er opbygget over rektangler og kvadrater og med en gennemgående nord-sydgående midterakse, der fortsætter i en smal allé til havens nordgrænse. Det sydlige rum, turneringspladsen, består af en græsflade, der på alle sider omsluttes af lindealléer. Den nordlige kvadratiske del består af tætklippede avnbøgehække gennemskåret af diagonale korsgange, der inddeler haverummet i en stram geometrisk stjerneformation, en såkaldt hækstjerne. Mod øst, på et lavere plateau, ligger en nyere rosenhave, anlagt fra 1980’erne. Et bindingsværkslysthus, opført i 1779 i forbindelse med anlæg af barokhaven, er fredet.
Christian Rosenkrantz nedlagde baroniet i 1811 og solgte året efter godset til et spekulationskonsortium. Samarbejdet ophørte dog allerede i 1813. Den ny eneejer, J.C. Schuchardt, lod Villestrup undergå en hårdhændet ombygning, hvor østfløjen, porttårnet, gavlene og de fleste af husets prydelser forsvandt.
Bygningen gennemgik adskillige restaureringer i 1900-tallet og fremstår i dag med sine røde mure som et trefløjet barokanlæg med bevarede renæssancedetaljer. Siden 1967 har ejendommen tilhørt Vincents Georg Iuul, en fjern efterkommer af 1500-tallets bygherre. Til godset hører godt 1.400 ha.
