Počátky feudálního sídla v Holešově sahají až do středověku. Lze tak soudit ze záznamů z r. 1245, kde je zmíněn biskupský leník Hugo z Holešova, který patrně sídlil na holešovské tvrzi. Až do husitských válek se na tomto panství vystřídalo několik osob, pravděpodobně v příbuzenské posloupnosti. Někteří z nich využívali holešovské tvrze jako základny pro své plenivé nájezdy na okolní panství. V době husitských válek byla tvrz zničena. Po husitských válkách dali Šternberkové vybudovat tvrz novou, ze které se v suterénu a přízemí dnešního zámku částečně dochovala její západní část, z níž je však patrno pouze několik detailů. Tvrz byla s největší pravděpodobností obehnána vodním příkopem.
V první polovině 16. století byla tvrz zvýšena o druhé, plochostropé patro. Z tohoto období se patrně dochovala půdorysná stopa, respektovaná pozdějšími přestavbami v jižní části zámku. O této pozdně gotické přestavbě však již nesvědčí žádné architektonické detaily, jelikož byly překryty radiální raně barokní přestavbou. Do roku 1574 byla pozdně gotická tvrz přestavěna na renesanční zámek, který byl, s největší pravděpodobností, dvoupatrový a respektoval půdorysnou stopu pozdně gotické tvrze. Třicetiletá válka zapříčinila přelom ve stavební historii holešovského zámku, kdy na jejím konci po roce 1643 byl zámek Švédy vypleněn a zapálen.
V takovém stavu jej r. 1651 koupil bohatý a vlivný hrabě z Rottalu, který si u vídeňského architekta Filiberta Luchesseho objednal přestavbu zámku. Podle jeho návrhu byla zahájena radikální přestavba. Od roku 1655 byla na místě původního zámku budována v duchu ranného baroka prakticky novostavba zámku nového. Hlavní stavební práce byly pravděpodobně dokončeny před r. 1674, kdy již hrabě z Rottalu na zámku bydlel. Podle Luchesseho návrhu vznikla tradiční, čtyřkřídlá, kolem vnitřního dvora uzavřená dispozice s polygonními nárožními věžemi. K výzdobě interiérů piana nobile a výzdoby saly terreny povolal hrabě z Rottalu malíře Cavalliho, jehož práce v sale terreně byly pravděpodobně později přemalovány. Druhé patro zámku však zůstalo nedokončené, otevřené přímo do krovu. K zámku příslušela i okrasná zahrada se vzrostlými alejemi a oranžerií, ovocný sad a v něm kuchyňská zahrada.
Na raně barokní stavební akce navázal ve vrcholném a pozdním baroku další hrabě z Rottalu, František Antonín (1717 - 1762). Za jeho éry panoval na zámku čilý kulturní i stavební ruch. Ještě před rokem 1750 dal upravit interiéry ve druhém patře vstupního křídla, starší vstupy do místností nahradil enfiládou, nechal provést nástěnné figurální malby. Ve velkém slavnostním sále severního křídla nechal zřídit zámecké divadlo. Tradici divadelních, operních a hudebních produkcí obnovil ve druhé polovině 19. století Rudolf Eugen Vrbna (1846 - 1883). Později dál sloužil až do konce feudální éry jako zimní zahrada. Zámecká kaple s hodnotným oltářem se sochami sv. Jana Nepomuckého a sv. Jana Sarkandra, pocházející patrně z dílny sochaře Bohumíra Fritsche, byla vybudována dodatečně Fr. Ant. Rotalem kolem poloviny 18. století vybouráním klenby mezi 1. a 2. patrem jižního křídla. Vnější podoba zámku se s několika změnami dochovala dodnes, pouze barevnost fasád byla odlišná, provedená ve světlých barvách, které celou rozsáhlou budovu opticky odlehčovaly. Přechod pozdního baroka v klasicismus ovlivnil jen úpravy interiérů druhého patra ve východním křídle, jehož pokoje byly taktéž propojeny enfiládou. Iluzivní malby v některých místnostech provedl bystřický malíř Jan Sviták (viz signatury). Na přelomu 18. a 19. století tím byly interiéry druhého patra konečně dohotoveny.
Poslední závažnější stavební změny spadají do období pozdního klasicismu, do poloviny 19. století. V této době bylo zavedeno zahradní rameno vodního příkopu a v souvislosti s tímto faktem byly zvětšeny a zaklenuty okenní otvory sally terreny, byla vybudována nová dominanta vstupního průčelí se znakem Bruntálských z Vrbna, nových majitelů zámku a změněna barevnost fasád, kterou dokumentuje současný stav. Další, již novodobé dílčí změny a zásahy v zámecké budově lze označit většinou za znehodnocující. Za zmínku stojí provedení secesních iluzivních maleb na stěnách některých místností druhého patra. Z této doby pochází konstrukce krovu a střecha. K zestátnění zámku došlo v roce 1948.