1964 жылы құрылды. Бұл Қазақстанда құрылған екінші көркемсурет музейі еді. Бұған дейін тек Алматыдағы Т. Г. Шевченко атындағы Қазақ мемлекеттік көркемсурет галереясы ғана болды. 1965 жылдың 18-ші желтоқсанында келушілерге музей өз есігін айқара ашты.

40 жылғы жұмысында музейде кескіндеме, графика, мүсін, сәндік-қолданбалы өнер бұйымдарының қайталанбас жинағы қалыптасты. Музей қорларында 5500-ден астам экспонаттар бар. Жинақтаманың ең маңызды бөлігі - қайнар көзінен бастап Республиканың кәсіби өнерінің қалыптасу, даму үрдістерін түпкілікті бейнелейтін Қазақстан суретшілерінің еңбектері (ХХ ғасырдың басында салынған Н. Г. Хлудовтың пейзаждары, оның шәкірттері А. Бортниковтың, Н. Соловьевтың, Қазақстанның тұңғыш халық суретшісі Ә. Қастеевтің шығармашылығы). Сонымен қатар музей жинағында 1930-шы - 40-шы жылдары Қазақстанда жұмыс істеген көрнекті шеберлердің шығармалары өз орнын тапқан (А. Черкасский, В. Эйферт, Л. Леонтьев, П. Зальцман, С. Калмыков және т.б.). 1960-70-ші жылдар - Қазақстанда мықты ұлттық мектептің қалыптасқан уақыты. Осы кезде А. Ғалымбаеваның, Қ. Телжановтың, А. Степановтың, С. Айтбаевтың, Г. Исмаилованың, Е. Сидоркиннің, Ж. Шарденовтың және т.б. авторлардың картиналары жазылды. 1980-90-шы жылдарда белсенді жұмыс істеген суретшілердің шығармалары қызықты (Е. Төлепбаев, К. Моллашев, А. Карпыков, Р. Хальфин және т. б.).

Музей коллекциясында Павлодардың алдыңғы қатарлы кәсіби суретшілері - Қ. Баймулдиннің, М. Колмогоровтың, Ғ. Қаржасовтың, П. Лысенконың, В. Мартынцевтың, А. Бибиннің, А. Гулиннің, Ө. Шурановтың, Ә. Игембаевтың және тағы басқаларының жұмыстары жинақталған. Павлодарда 1919 жылдан 1929 жылға дейін тұрған белгілі орыс суретшісі В. П. Батуриннің (1863-1938) картиналары жинақтаманың мақтанышы болып табылады.

1990-шы - 2000-шы жылдардың басында Қазақстанның көркем өмірінің қазіргі үрдістерін бейнелей отырып, Павлодар облыстық көркемсурет музейі коллекциясын кеңейтіп, өз дамуын жалғастырып келеді.

Жыл сайын музей 15-тен астам экспозиция ұсынады. Бұл музей қорларынан алынған дәстүрлі тақырыптық іріктемелері, павлодарлық суретшілердің есептік және жеке көрмелері, фотокөрмелер, «М*АРТ» жастар жобасының көрмелері, балалар суреттерінің көрмесі, алдыңғы қатарлы музейлердің жинақтарынан алынған көшпелі көрмелер.

Музейде өткізілетін суретшілермен кездесулер, мастер-класстар, экскурсиялар, көркем-әдеби және музыкалық кештер, презентациялар, бейнелеу өнері тарихы бойынша видеофильм көрсетілімдері ерекше қызығушылық тудырады. Музей кеңес беру-сараптау қызметтерін көрсетеді, қала және облыстың оқу мекемелері үшін білім беру бағдарламаларына белсенді ат салысады. Музей әріптестіктерінің ішінде тек Қазақстан музейлері мен галереялары ғана емес, сонымен қатар Омбы мен Новосібір музейлері, Британ Кеңесі, Гете Институты, Сорос-Алматы қазіргі заман өнер орталығы, Халықаралық «Ашық музей» Ассоцияциясы (ХАА), Ресей музейлерінің Ассоцияциясы (РМА) бар.