Основная экспозиция музея размещена в здании, которое является памятником архитектуры, расположенном по улице Ленина. Построено в 1890-х гг. В нем размещались магазины купца первой гильдии А.Дерова. Администрация, внутренние отделы расположены на втором этаже старинного здания - бывшей почтово-телеграфной конторы. Основное фондохранилище расположено в отдельном здании, являющемся памятником архитектуры, по улице Ленина, 129.
Павлодарский областной историко-краеведческий музей был основан в 1942 году на базе областного отделения «Общества изучения Казахстана». В 1959 году ему было присвоено имя Г.Н.Потанина - земляка, уроженца с. Ямышево, путешественника, исследователя Средней Азии. Основателем музея был фотограф, краевед Дмитрий Поликарпович Багаев. Экспозиция музея располагается в 12 залах, раскрывающих историю и культуру нашего края. Имеется научная библиотека и шесть филиалов: Дом-музей Д.П. Багаева, музей песенного творчества им. М.Шамсутдиновой, Музей Войнской славы, КГКП «Экибастузский историко-краеведческий музей», КГКП «Аксуский историко-краеведческий музей», КГКП «Щербактинский историко-краевеческий музей». Работает музей под открытым небом.
Большой гордостью и творческим показателем работы музея являются его фонды. Коллекция фондов музея из года в год пополняется, совершенствуется их научная обработка. В фондах музея насчитывается более ста тысяч экспонатов.
Основу собрания музея составляют коллекции: археологическая, палеонтологическая, этнографическая, нумизматика, фотоизобразительная коллекция, документальная, естественно-научная, производственная, оружие - огнестрельное и холодное.
Наряду с лекционной и экскурсионной работой музей организует презентации выставок из фондов республиканских музеев, из собственных фондов. Проводятся научно-практические конференции, семинары международного и регионального уровней, ежегодные «Потанинские чтения», мастер-классы, краеведческие уроки, лекции-концерты, творческие вечера.
На базе областного историко-краеведческого музея проводятся археологические и этнографические экспедиции по исследованию Павлодарского Прииртышья.
Партнерами музея являются Музей первого Президента РК (г. Астана), Музей золота РК (г. Астана), Государственный историко-краеведческий музей (г. Омск), Институт археологии и этнографии Сибирского отделения РАН, Институт археологии им. А.Маргулана, Центральный Государственный музей, краеведческие музеи гг. Кокчетав, Караганда, Усть-Каменогорск и др.
В 2019 году павлодарский областной историко-краеведческий музей им. Потанина признан лучшим государственным музеем Республики на фестивале «Рухани қазына» в Нур-Султане, который собрал более 200 работников культуры и искусства со всего Казахстана.