Учрежден 24 февраля 1905 г. губернским статистическим комитетом как музей Северного Кавказа краеведческого профиля. Региональный статус определялся исторической ролью губернии на Юге России, – долгое время Ставрополье было центром Северного Кавказа.

Инициатором создания музея выступал присяжный поверенный, известный общественный деятель, ревнитель старины Григорий Николаевич Прозрителев. Являясь структурным подразделением Ставропольского губернского статистического комитета, музей функционировал в тесной связи со Ставропольской учетной архивной комиссией. Он располагался в здании губернского правления и имел следующую структуру.

1 – естественно-исторический отдел с подотделами геологии, минералогии, палеонтологии, зоологии и ботаники.

2 – этнографический отдел с подотделами антропологии и этнографии.

3 – исторический отдел с подотделами археологии и нумизматики.

4 – сельскохозяйственный отдел с подотделами земледелия, полеводства, животноводства, лесоводства и лесоразведения, садоводства, огородничества, виноградарства и виноделия, пчеловодства, шелководства.

5 – санитарно-гигиенический отдел.

6 – отдел народного образования.

7 – отдел кустарной и заводской промышленности.

К началу Первой мировой войны коллекции музея Северного Кавказа насчитывали более 10 тысяч единиц хранения. При музее существовала научная библиотека, составлявшая к 1914 г. 1710 томов книг по краеведению и истории. Экспозиция включала в себя исторический и природоведческий разделы. В первом была представлена древняя и средневековая история региона, материалы Кавказской войны и времени освоения Северного Кавказа. Наиболее интересными и познавательными были этнографические комплексы, реконструирующие элементы и быт народов, населявших северокавказский регион. Особую ценность представляла коллекция кавказского оружия, в основе которой было собрание, подаренное музею Г.Н. Прозрителевым.

В естественно-исторической части демонстрировались палеонтологические находки, чучела животных, образцы минералов и растительного мира; выделялся на этом фоне сельскохозяйственный раздел. На базе музея велась активная исследовательская и научно-просветительская деятельность.

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

В период гражданской войны и в первые годы Советской власти в музей поступили собрания художественных произведений, реквизированных у состоятельных граждан. Были приняты на хранение предметы из Тифлисского музея  «Храм Славы» и упраздненного епархиального музея, поступили коллекции из некоторых музеев Москвы и Ленинграда.

В 1927 г. музей Северного Кавказа и городской музей были слиты в одно учреждение, расположившееся в здании бывших торговых рядов, где музей находится и поныне.

В 1930-е годы структура музея оформилась в соответствии с идеологическими установками того времени. Он состоял из трех отделов: исторический, отдел социалистического строительства и отдел природы. В эти годы музей пополнился коллекциями из Ростовского музея горских народов.

В 1939 г. по поручению партийных органов на базе краеведческого музея начинается создание антирелигиозного музея, который разместился в здании армянской церкви.

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

Представителями немецкой комендатуры были изъяты все предметы религиозного культа, собранные для антирелигиозного музея. После освобождения Ставрополя комиссия подсчитала, что потери составили 12 тысяч музейных предметов и 2375 книг на общую сумму 4559580 рублей. Ущерб в связи с утратой материальных ценностей оценивался в 500000 рублей. Однако основа музея, благодаря самоотверженным действиям сотрудников и прежде всего заведующей историческим отделом Т.М. Минаевой, была сохранена.

В течение всей войны, включая оккупацию, музей не закрывался и работал, невзирая на трудности.

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

В 1962 г. на основе художественного отдела музея учреждается краевой музей изобразительных искусств.

В 1979 г. во главе со Ставропольским краеведческим музеем создается музейное объединение, в которое к 1996 г. входило 19 филиалов, образованных на базе бывших общественных музеев в городах Невинномысск, Минеральные Воды, Кисловодск, Ессентуки, Железноводск, Пятигорск, Георгиевск, Зеленокумск, Ипатово, Благодарный, Светлоград, Изобильный, в селах Александровском и Донском. Четыре филиала располагались в Ставрополе – Дом семьи Лопатиных, усадьба художника В.И. Смирнова с мемориалом К.Л. Хетагурова, картинная галерея художника П.М. Гречишкина, археологический и природный музей-заповедник Татарское городище. Объединение заложило равномерно распределенную краевую музейную сеть.

В 1997 г. музейное объединение было реформировано, и филиалы в городах и селах стали самостоятельными музеями. Филиалы, расположенные в Ставрополе, получили статус отделов.

В 1970 г. музею было присвоено имя одного из основателей – Г.К. Праве, а с учетом уточненной истории музея  (1993 г.) ему присвоили потом и имя Г.Н. Прозрителева.

До середины  XX в. в составе музея находилась публичная библиотека, которая в 1950-х годах составила основу краевой научной библиотеки им. М.Ю. Лермонтова.

В 1984-1986 гг. двухэтажное  здание музея было надстроено, а старые экспозиции демонтированы. В течение 1990-х годов на новых площадях создаются экспозиции по истории и этнографии Ставрополья XVIII-XX вв., вводится современная экспозиция по геологии и палеонтологии, в стадии разработки находятся экспозиции по археологии и природному миру.

Особенностью работы музея в этот период является активная выставочная деятельность, как из собственных собраний, так и привозных коллекций.

В последней четверти XX в. музей активизирует археологические, историко-этнографические и природоведческие экспедиции.

Собрания музея отражают его историю и отличаются многообразием, охватывая не только Ставрополье, но и весь Северный Кавказ. На 1 января 2005 г. основной фонд насчитывал 199615 единиц, научно-вспомогательный – 59871 единицу.

Около 40 % коллекций составляет фотодокументальный фонд, довольно полно отражающий прежде всего историю XX в. На мировом уровне оценивается палеонтологическая коллекция. В области естественной истории большой научный интерес представляют ботаническая, энтомологическая, зоологическая и минералогическая коллекции.

Значительный удельный вес занимает археологическая коллекция. Выделяются коллекции оружия, учебных наглядных пособий, плакатов,  нумизматики, картографии, этнографии.

Весь состав фонда компьютеризирован и переведен на автоматизированный учет.

В перспективе предусматривается преобразование музея из краеведческого в историко-культурный и природно-ландшафтный музей-заповедник.