Anglický přírodně krajinářský park obklopující zámek v Lešné vznikl pod vlivem dobového romantického cítění v polovině 19. století. Už před jeho zřízením se jižně od hospodářského dvora rozkládala okrasná zámecká zahrada užitkového rázu, na jejímž půdorysu byly vysázeny tehdejším majitelem Jiřím Beesem nejstarší dřeviny domácího původu (např. jasan, habr, lípa) doplněné cizími listnáči (jerlín, dřezovec) a jehličnany (douglasky, modříny a tsugy kanadské).

O další rozkvět zámeckého parku se v 80. a 90. letech 19. století zasloužili noví majitelé panství, císařský komoří August hrabě Kinský a jeho syn Filip. Byla zde vysazena řada introdukovaných dřevin (např. turecké lísky, cypřišky, katalpa, břestovec, liliovník, pterokarye, nahovětvec...). Kinští udržovali park i zámek na velmi dobré úrovni a celý areál byl neustále vylepšován: byla zvelebena nedaleká obora se zvěří, založena ovocná školka a postaveny tři skleníky. Zavedení nového vodovodu (1894) umožnilo vystavění kulatého bazénu s vodotryskem před zahradním průčelím zámku. V meziválečném období vznikl vykácením vzrostlých dřevin průhled přes alej na oboru se zvěří, osázený rododendrony a azalkami. V roce 1925 byly založeny dva rybníčky a bažantnice a ke zvýšení exkluzivity přispělo zbudování tenisového kurtu a kuželny.

Konfiskace majetku hraběcího rodu Kinských v roce 1945 vedla k postupné devastaci areálu. Nastal jeho úpadek trvající až do začátku 70. let 20. století. Do parku byl volný přístup, nebyla prováděna pravidelná péče o dřeviny, nebyly vysazovány nové keře a stromy, park zarostl náletovými dřevinami. Místní JZD dokonce v parku zřídilo silážní jámu. Celé toto bezvládí mělo nesporný vliv i na zdravotní stav dřevin v parku. Mnohé stromy uschly a bylo nutno je vykácet. Velké množství náletových dřevin potlačovalo růst dřevin kultivovaných, nedostatečnou údržbou uhynulo mnoho stromů.

V roce 1975 přešel park pod správu Okresního vlastivědného muzea ve Vsetíně, které zahájilo od roku 1985 jeho cílenou regeneraci. Zaměřena byla na pěstební opatření, proběhla sanace starých dřevin, výsadba nových, oprava oplocení a zdi ohraničující park a také likvidace černých skládek. Byla zrušena kašna, která neplnila od roku 1975 svou funkci. K velké rekonstrukci a revitalizaci parku došlo až se získáním dotace ze Státního fondu životního prostředí ČR na konci prvního desetiletí 21. století. Byly realizovány asanace dlouholetého dřevinného náletu a především množství nových výsadeb. Za dobu rekonstrukce bylo vykáceno 894 stromů (nad průměr 10 cm) a vysazeno 2 354 kusů nových dřevin. Celkové náklady na rekonstrukci parku za dobu správy muzea činí téměř 6 miliónů Kč.

Dlouholetá péče a starost o celý objekt byla zakončena slavnostním otevřením parku veřejnosti dne 1. 10. 2000. Symbolické přestřižení pásky provedly osoby nejpovolanější, pan Christian Kinsky z Heidenreichsteinu a jeho sestra Elisabeth Kinsky, zástupci rodu Kinských z Vchynic a Tetova, který byl posledním šlechtickým vlastníkem a zvelebitelem tohoto krásného parku.