I nordkanten af Lille Vildmose ligger den lysåbne Høstemark Skov. Området var i stenalderen dækket af Littorinahavet, og skoven ligger således på gammel havbund. I jernalderen blev dele af skoven ryddet og opdyrket, men da dyrkningen ophørte omkring 200‑400 e.Kr., sprang området på ny i skov. Før Reformationen tilhørte skoven Viborg bispestol, men overgik herefter til kronen. I 1674 kom skoven i privat eje. Skovområdet har fået navn efter den tidligere herregård Høstemark, som blev oprettet i 1696 ved samkøb af gårdene i Høgsted. I 1898 blev herregården frasolgt, men skoven forblev i privat eje indtil 1988, hvor den sammen med Høstemark Mose blev opkøbt af Aage V. Jensens Fonde.
Høstemark Skov blev indhegnet som dyrehave 1933‑34, og af hensyn til naturplejen, som varetages af kronvildt, har man siden valgt at opretholde indhegningen. Området dækker et areal på 574 ha, som omfatter både nåle- og løvskov samt lysåbne enge, græssletter, rydninger og moser.
Med undtagelse af skovfyrrene er nåleskoven under afvikling til fordel for løvskov, vådområder og naturlig tilgroning. I løvskoven foregår der ikke nogen nævneværdig hugst. Driften sker med stort hensyn til fugle- og vildtbestanden. Tidligere har der været drevet løvengsdrift, græsning og muligvis svin på olden i skoven. Græsningspræget fra den kreaturgræsning, som fandt sted fra 1800-tallet og frem til 1940’erne, er siden 1934 opretholdt ved hjortegræsning. Rødel er almindelig i skoven og danner ellesump i de fugtige lavninger. Mange af elletræerne er mangestammede, hvilket viser, at skoven helt op til 1940’erne har været drevet som stævningsskov. Den sumpede skovbund har et rigt planteliv, som bl.a. omfatter engkabbeleje, vandrøllike, gul iris, storblomstret kodriver og skovspringklap samt mange bregnearter. Derudover har skoven en usædvanlig svampeflora.
Den egentlige græsningsskov i Høstemark Skov er en blandskov af især dunbirk, rødel, eg, bøg og ask med en underskov af kristtorn, hassel og alm. hæg. Skoven er lysåben og giver et godt indtryk af, hvordan skovene så ud før Fredskovsforordningen af 1805. I denne del af skoven kan man i skovbunden finde planter som hønsebær, skovrørhvene, spidsbladet steffensurt og storblomstret kodriver.
Områdets sletter holdes åbne ved høslæt og hjortegræsning, og her kan det gamle, artsrige rimme-doppelandskab med vekslende tørre strandvolde og fugtige lavninger tydeligt ses. Sammen med bl.a. strandkogleaks vokser her også mere usædvanlige plantearter som bregnerne alm. månerude og slangetunge.
Ud over et rigt planteliv har Høstemark Skovs varierede natur også dannet grundlag for et mangfoldigt dyreliv. Især sommerfuglene gør sig bemærkede ved deres artsrigdom, og alene dagsommerfuglene er repræsenterede ved 46 forskellige arter. Også fuglelivet er både rigt og veldokumenteret, da der siden 1984 regelmæssigt er foretaget optællinger af skovens vinter- og ynglefugle. De viser, at skoven bl.a. huser en af landets tætteste bestande af hulrugende fugle som rødstjert, træløber, stær og huldue samt en række forskellige fluesnappere, mejser, spætter og ugler. Derudover har et kongeørnepar siden 2003 hvert år opfostret en unge i skoven. Kun i 2017 udeblev ynglesuccesen.
Høstemark Skov har en stor bestand af krondyr, som inden for indhegningen holdes på en bestand på ca. 170 individer. Dertil kommer store bestande af både rådyr, grævling og hare, ligesom også ræv, odder, skovmår, husmår, ilder, lækat og brud findes i skoven. Der er registreret otte arter af flagermus fra Høstemark Skov, heriblandt de sjældne Brandts flagermus og frynseflagermus.
Høstemark Skov indgår i den 7.700 ha store fredning af Lille Vildmose fra 2007. Derudover er skoven en del af habitatområdet Lille Vildmose, Tofte Skov og Høstemark Skov samt af fuglebeskyttelsesområdet Lille Vildmose.
