Музей тарихын әріден қарайтын болсақ, бұл XX ғасырдың басында дүниеге келген еді. 1923 жылғы тамыз айында Петропавл қаласында «жергілікті өлкені зерттеу жөніндегі Ақмола губерниялық қоғамы» құрылды, оған музей құрудың бастамашылары: И.Г. Чернядьева, И. Г. Лобова, К. А. Александрова кірді.

1924 жылдың қаңтарында мұражай ресми түрде ашылды. Бастапқыда ол Караванная (қазіргі К. Сутюшев көшесі) көшесіндегі шағын үйде орналасқан. Мұражайдың алғашқы директоры болып бұрынғы мұғалім, өлкетанушы Дьячков Иван Прокопьевич тағайындалды. Губерниялық атқару комитетінің шешімі бойынша мұражайға Коммунистический (казіргі Мағжан Жұмабаев көшесі) көшесінен үй берілді.

1925 жылдың жазында И.П. Дьячков экспедицияға қатысып, мұражайға бірқатар этнографиялық және геологиялық материалдарды әкелді. Экспонаттарды жинаумен қатар мұражай қызметкерлері қала өміріне белсенді қатысады. 1925 жылы жер бөлімімен бірге оның аумағында үш күн ішінде бес мыңнан астам адам қатысқан ауылшаруашылық көрмесі өтті.

1926 жылдың аяғында (қазан айында) мұражайда жергілікті аймақты сипаттайтын 1182 экспонат болды. Осы жылдың 112 күнінде келушілер саны 19 983 адамға жетті. 1928 жыл бір өте құнды табумен ерекшеленді. Щучинск ауданының Бармашино шатқалынан 2 шақырым жердегі тас карьерден салмағы 40,5 центнер плитаның астынан адамның бас сүйегі, қола қазан, мыс пышақ, 11 мыс жебе ұштары, 15 алтын пластина табылды. Табылған зат үлкен археологиялық және материалдық құндылыққа ие болды және сол жылы зерттеу үшін Мемлекеттік орыс мұражайына жіберілді. Оны белгілі Ленинград археологы Бернштам сипаттаған.

Мүлікті тәркілеуге байланысты 30-шы жылдары мұражайға қазақ тұрмысының бірнеше заттары, бас киім-сәукелесі, сыйға тартылған дворян грамотасы, үй жабдықтары, тоқыма станогы, фотосуреттер, құжаттар, қару-жарақ, археологиялық заттар берілді.

Алғашқы мұражай коллекциялары экспедициялар нәтижесінде пайда болды. Бұл негізінен археология, этнография, табиғи – биологиялық коллекциялар, минералды үлгілер болды. Сонымен бірге ғылыми кітапхана құрыла бастады, оның қорына ескі баспа кітаптары түсті. Музей үнемі Омбы, Ақмола, Ленинград сияқты басқа музейлермен қосарлас материал алмасуды жүзеге асырды.

Мұражайға келушілер саны жылдар өте арта берді: 27/28 жылдары келушілер саны 36750 адамды құрады, 28/29 жылдары – 61 200 адам. Мұражайға келушілер оқушылар, шаруалар, қала халқының түрлі топтарының өкілдері болды. Алғашқы коллекциялар Вознесенский соборының ғимаратында орналастырылды (бұл ғимараттағы мұражай 1931-1934 жылдары орналасқан).

1934 жылы мұражай директоры Русаков Борис Васильевич болды. 1934 жылы мұражай Советская көшесіне көшірілгеннен кейін материалдарды жүйелеуге және оларды көпшілік назарына ұсынуға мүмкіндік алды. Бұрын бір қабатты кірпіш үйде американдық Зингер және К тігін машиналарының дүкені болған (ғимарат сақталмаған). Мұражайдың үш бөлімі болды: табиғи-тарихи, мәдени-тарихи және қоғамдық-экономикалық.

1937 жылы мұражайды М.К.Раздобреева басқарады, 1943-44 жылдары мұражайды Гершовский басқарады.

1947 жылдан 1982 жылға дейін тарихи-өлкетану мұражайының директоры Константин Сергеевич Ушков болып табылады. Оның күш-жігерінің арқасында мұражайда коллекцияларды жүйелеу, кітапхана қорын ретке келтіру жүрді, көрнекті ғалымдарды тарта отырып, коллекцияларға ғылыми сипаттама жүргізілді. Жаңа экспонаттарды жинау белсенді жүргізілуде, мұражай жұмысын жетілдіру бағдарламалары әзірленуде.

1949 жылдың қыркүйек айынан бастап мұражайда антрополог-зерттеуші Антонас Пошка аға ғылыми қызметкер лауазымында жұмыс істейді (1945 жылы А. Пошка Вильнюс қаласындағы Ұлттық кітапханасының директоры қызметінен алынып, «неміс-фашист басқыншыларымен ынтымақтастығы» үшін сотталды).

А.Пошка Қаз ССР Академиясының экспедициясы жүргізген қазба жұмыстарына қатысты. Сол кезде Петропавлдан 15 шақырым жерде (Ольшанка ауылының маңында) Есіл өзенінің жағасында мастодонттың қаңқасы табылды. Қаңқа қайта қалпына келтіріліп, Қазақстан Ғылым Академиясының палеонтологиялық мұражайында орналасқан. Сол жылы (1952) Антонас Пошка отанына оралды.

1949-50 жылдары мұражайдың аға ғылыми қызметкері болып белгілі ғалым, КСРО Ғылым Академиясының археология секторының меңгерушісі, Тарле шәкірті Александр Игнатьевич Семенов жұмыс істеді. Ол мұражайда кеңеске дейінгі кезеңнің экспозициясын жасады, өлкенің тарихын зерттеумен айналысты, Солтүстік Қазақстан тарихы бойынша бірнеше маңызды еңбектер жазды. А.И. Семенов Солтүстік Қазақстан облысының алғашқы археологиялық картасын, метрикалық және тарихи-революциялық ескерткіштердің картасын жасады. Оның тікелей басшылығымен Половной көлі мен Багаты өзенінде археологиялық қазба жұмыстары жүргізілді. 1957 жылы Қазақ КСР Ғылым Академиясы Солтүстік Қазақстан аумағында археологиялық қазба жұмыстарын жүргізген кезде А.И.Семенов құрастырған карта пайдаланылды.

1950 жылы мұражай жергілікті суретшілердің туындыларын, атап айтқанда көрнекті Ленинградтық суретші Сергей Райхенбергтің «Владивостокский порт», «Яблони в цвету», «Разлив реки Ишим», «Петропавловская крепость», «Петропавловск строится» туындыларын сатып алды. Қуғын-сүргінге Колымаға қуғынға ұшыраған С.Райхенберг одан әрі мерзімін өтеу үшін 1949 жылы Владивостокқа, одан кейін Петропавлға ауыстырылды. Облыстық театрдың бас суретшісі болып жұмыс істеді. 1951 жылы мұражай залдарында оның бастамасы бойынша Петропавлдағы алғашқы көркем көрмелердің бірі өтті, оған Эстониядан келген мүсінші А.Эллер, А. Райхенберг, С. Фурсе, Петр Сысолов қатысты. Бұл оқиғаның кішігірім провинциялық қала үшін маңызы зор болды.

Сол жылдары Петропавлда қуғын-сүргінге ұшыраған Александр Сергеевич Эллер мерзімін өтеп жатты. Мұражай дирекциясының тапсырысы бойынша А.Эллер қазақ ағартушылары мен көрнекті қайраткерлері: Шоқан Уәлиханов, Абай Құнанбаев, Жамбыл Жабаев, Ыбырай Алтынсариннің мүсіндік портреттерін жасаған. Эстон шеберінің жұмыстары мұражайда сақтаулы. Қордың одан әрі өсуі 1951 жылы бейнелеу өнері бөлімін ашуға мүмкіндік берді, ол 1989 жылы жеке мұражайға айналды.

1968 жылы мұражай жаңа ғимарат алды. Қарағанды және Целиноград көркемөнер қорларының суретшілер тобы суретші А.М. Чудовтың басшылығымен ертеде көпес Туби Лейбович Аркельге тиесілі екі қабатты үйге қайта өңдеу жүргізді (19 ғ.аяғы). Ғимарат мұражай экспозициялық алаңын кеңейту қажеттілігіне байланысты ұсынылған. Осы уақытқа дейін мұражайда өлке тарихы туралы үлкен материалдар жинақталды.

Мұражай ішінен Солтүстік Қазақстан археологиялық экспедициясы құрылды, оның жұмыс жасау кезеңінде 600-ден астам археологиялық ескерткіш ашылып, жартылай зерттелді. 1981 жылы мұражайда археологияның ғылыми-зерттеу бөлімі ұйымдастырылды.

1982 жылы мұражайға көпес М. Ф. Стреловтың екі қабатты үй мен қойма бөлмелері берілді (19 ғ. аяғы). Қалпына келтіру жұмыстарынан кейін ғимараттарды біріктіріп, екі қабатты кірпіштен салынған негізгі корпусқа қосылды.

2005 жылы «Казреставрация» кәсіпорын мамандарымен ғимараттарға күрделі жөндеу жұмыстары жүргізілді, экспозицияның құрылысын А.Жансүгіров басқарған «Дара» фирмасының суретшілері мен дизайнерлері жүзеге асырды. 2005 жылдың 27 қарашасында жаңартылған мұражай ашылды. Экспозиция алаңы 2000 шаршы метрді құрады.

2006 жылғы 6 қыркүйекте мұражайға Қазақстан Республикасының Президенті Н.Ә. Назарбаев келді. Ол мұражайға жоғары баға беріп, оны Республиканың ең жақсы мұражайларының бірі деп атады.

Келушілердің назарына 13 зал ұсынылды. Экскурсия табиғат залынан басталады. Одан әрі өлкенің ежелгі тарихының 4 залы бар, онда бірегей археологиялық топтамалар көрсетілген.

Экспозицияда ежелгі Еуразия орталығында ең алғаш жылықыны қолға үйреткен Ботай қонысының және Байқара обасы – скифтердің ғибадатханалық кешені сияқты бірегей археологиялық ескерткіштердің материалдары қойылған. Сондай-ақ кейінгі көшпенділердің тарихы туралы археологиялық материал: ғұндар мен моңғолдар. Экспозицияда өлкенің бүкіл тарихы, оның ішінде тарихтың қайғылы беттері: революция, Азаматтық соғыс, қуғын-сүргін және т. б. көрсетілген.

Ұлы Отан соғысының тарихына, 314 атқыштар дивизиясының жауынгерлік жолына лайықты орын берілген. Экспозицияда жеке заттар, марапаттар, киім-кешек көрсетілген. Мұражай - тың жерлерді игеру тарихы бойынша бай материал жинақтады.

2012 жылы ҚР Тұңғыш Президентінің залы ашылды. 2016 жылы «Қазақ мемлекеттілігінің құрылуы мен қалыптасуы. Қазақ этнографиясы» және «Солтүстік Қазақстан облысы Тәуелсіздік жылдарындағы тарихы. Қазақстан халқы Ассамблеясы» жаңа экспозиялары ашылды.