Holstebro Kunstmuseum blev indviet i 1967. Tobaksfabrikant Søren Færchs gamle patriciervilla i nybarok palæstil, der var tegnet af Andreas Clemmensen, danner rammen om museet. Statsanerkendelsen blev tildelt kort efter indvielsen, og museet fik sidenhen status som selvejende institution med Holstebro Kommune som hovedbidragyder.
Holstebro Kunstmuseums første leder var kunsthistorikeren og forfatteren Poul Vad, som få år forinden ved Statens Kunstfonds mellemkomst var blevet ansat som kommunens kunstneriske konsulent. Da der ikke eksisterede kunstsamlinger i området, der meningsfuldt kunne danne basis for et museum, blev det Vads opdrag at formulere et idégrundlag for den nyoprettede institution. Hans målsætning blev efterfølgende i kraft af indkøb, deponeringer og lån at opbygge et kunstmuseum, der skilte sig ud fra de øvrige danske provinsmuseer. Ønsket var således ikke at satse på egnens kunstnere, men snarere i kraft af få, velvalgte eksempler at etablere en samling, der gik på tværs af de billedkunstneriske udtryksformer i tid og rum.
Vad orienterede sin indsamlingspolitik langs tre akser: moderne dansk kunst fra ca. 1930 og frem med retrospektive samlinger af et begrænset antal udvalgte kunstnere, hvilket tillader, at disse kan studeres fyldestgørende; udenlandsk grafik af internationalt tilsnit samt afrikansk kunst. Hermed ville Vad præsentere modernismen i dybden og bredden og ikke mindst anskueliggøre den afgørende rolle, som såkaldt primitiv kunst har spillet i 1900-tallets kunstneriske bevidsthed.
Vads foretrukne valg blandt samtidens danske kunstnere var den lyriske naturalist Lauritz Hartz, den fabulerende naivist Henry Heerup, den abstrakte surrealist Ejler Bille samt eksperimentalkunstneren Albert Mertz. Inden for skulpturen fokuserede Vad især på Astrid Noack og Erik Thommesen, hvis værker repræsenterer tidløse aspekter af menneskefremstillingen i billedhuggerkunstens historie i spændet fra naturalisme over abstraktion. I dag huser Holstebro Kunstmuseum også Astrid Noacks studiesamling, der bl.a. omfatter en lang række originale gipsmodeller. Kunsthåndværket blev repræsenteret bl.a. ved keramikerne Ursula Munch-Petersen, Gutte Eriksen og senere Gertrud Vasegaard samt tekstilkunstneren Anna Thommesen. I mangt og meget kendetegnes de historiske dele af museets samlinger ved forbindelsen mellem avantgardesammenslutningen Linien, der eksisterede i perioden 1934‑39, og den senere, mere traditionsforbundne kunstnersammenslutning Martsudstillingen, der var aktiv 1951‑82. Flere af museets markante skikkelser var initiativtagere til og medlemmer af begge grupperinger, heriblandt Ejler Bille og Erik Thommesen.
Samlingen af udenlandsk grafik blev fra begyndelsen udgjort af Marc Chagall, Alberto Giacometti, Pablo Picasso og Henri Matisse, mens den omfattende afrikanske samling var en testamentarisk gave fra billedhuggeren Poul Holm Olsen. Øvrige donationer er sidenhen kommet til, bl.a. en samling af præcolumbiansk keramik fra Peru skænket af zoologerne Marie og Ole Hammer samt en samling af balinesisk kunst, som blev foræret til museet af billedkunstnerne Ejler Bille og Agnete Therkildsen.
Samlingernes hovedlinjer er i årenes løb blevet konsolideret og udbygget. Grafiksamlingen tæller i dag papirarbejder af Francisco de Goya og Francis Bacon. De mere naturbestemte kunstneriske udtryk i samlingen udgøres af John Olsen, Kirsten Klein og Inge Lise Westman samt glaskunstnere som Tobias Møhl og Pipaluk Lake. Dertil råder Holstebro Kunstmuseum i dag over en af de mest repræsentative samlinger af den internationalt anerkendte danske kunstner Tal R og en større mængde værker af Peter Linde Busk. Forbindelsen til globalkunsten er også blevet udbygget med værker af tværkulturelt arbejdende kunstnere som Sonja Ferlov Mancoba, Martin Erik Andersen og Emil Westman Hertz. Dertil er samlingerne siden år 2000 blevet præget af en tiltagende internationalisering med værker af konceptkunstneren Lawrence Weiner samt to af samtidsmaleriets hovedeksponenter: tyskerne Jonathan Meese og Daniel Richter. En omfattende samling af Olivia Holm-Møllers værker har i dag hjemsted på Holstebro Kunstmuseum som et resultat af, at Jens Nielsen & Olivia Holm-Møller Museet ophørte i 2013.
I hhv. 1981 og 2011 er Holstebro Kunstmuseum blevet udvidet med større tilbygninger af Hanne Kjærholm. Siden 1992 har kunstmuseet delt bygningskompleks med Holstebro Museum.
