Первая экспозиция для посетителей открылась 1946 году. Основную массу музейных экспонатов составляли исторические фотографии Д.П. Багаева, посвященные природе и истории края. Из других экспонатов были представлены кости древних животных, обнаруженные при раскопках палеонтологического памятника неогенового периода «Гусиный перелет», каменное изваяние из Баянаульского р-на, надгробная плита XIX в., конская сбруя, отдельные фрагменты древней керамики и каменные орудия труда древнего человека.

В течении 1950-х гг. в экспозиции формируются основные разделы, связанные с историей и природой края, разделы по археологии, палеонтологии, а также этнографический уголок. В эти же годы проходят первые разведочные археологические экспедиции в районе старого Экибастуза и Баянаульском р-не. В ходе работ велся сбор информации о количестве памятников, фотофиксация и зарисовка курганов, сбор подъемного материала с древних поселений. В работе принимали участие сотрудники музея Л. Сафонова, Л. Багаев и М. Гапон.

В 1959 г. историко-краеведческому музею присваивается имя Г.Н. Потанина, путешественника и исследователя Средней Азии, уроженца Павлодарской области. В советский период Павлодарский областной историко-краеведческий музей им. Г.Н. Потанина превратился в самое большое хранилище экспонатов по истории Павлодарской области с широким хронологическим и тематическим диапазоном.

В 1998 г. директором музея становится павлодарский археолог В.К. Мерц. При нем в 2000 г. начинается реновация экспозиции музея. В 2010 году музей приобретает более выразительную экспозицию. Помимо основных разделов по природе края, палеонтологии, археологии, этнографии, истории города, открывается новый зал, посвященный истории Казахского государства XVII-XIX вв., где широко отражена борьба казахского народа против Джунгарского ханства. В настоящее время экспозиция музея размещается в 12 тематических залах и охватывает историческое и культурное развитие Павлодарского Прииртышья с древнейших времен до современности.

Основная экспозиция музея расположена в историческом здании конца XIX века, являющемся памятником архитектуры. Особая гордость музея – научные фонды. В настоящее время основное хранилище насчитывает более 144 тысяч единиц хранения. Коллекции регулярно пополняются и систематизируются в ходе научной обработки. Одно из приоритетных направлений деятельности музея – научно-исследовательская работа. Сотрудники разрабатывают тематические лекции по истории региона, палеонтологии, археологии и этнографии. Организуются археологические и этнографические экспедиции, результаты которых изучаются и готовятся к экспонированию. Если до середины 1990-х годов археологические коллекции формировались практически исключительно из числа случайных находок, которые приносили в музей жители Павлодара и Павлодарской области, то с 1995 года, коллекции все больше поступают из археологических раскопок.

В последнее время музей все больше внедряет достижения цифровых технологий. В 2019 году музей запустил проект по оцифровке памятников археологии с помощью цифровой фотограмметрии. Десятки памятников древнего искусства, включающие наскальные рисунки, каменные стелы и средневековые изваяния были оцифрованы с переводом их в 3D-формат.