Решение о создании музея принято учредителем — Кисловодским краеведческим обществом — 17 сентября 1962. Основан 3 мая 1963 (дата первой записи в музейном акте приема экспонатов), открыт 9 мая 1965. Государственный статус получил на основании Постановления Министерства культуры РСФСР 1970 г. С 1971 — филиал Ставропольского государственного краеведческого музея им. Г.К. Праве (с 1991 г. — им. Г.Н. Прозрителева и Г.К. Праве). С 1998 — муниципальный музей с современным названием.

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

Инициаторами создания музея явились члены Кисловодского краеведческого общества (осн. в 1962): братья Б.С. и Е.С. Виноградовы, В.Е. Брансбург, Ю.А. Конжухарь, Н.Н. Михайлов, В. Никитин, И.Т. и Я.М. Тулиновы и другие. В их деятельности прослеживается преемственность с деятельностью Музея городского филиала Кавказского горного общества (1917), первого в Кисловодске. Большую помощь в организации музея сыграли профессиональные ученые-археологи, особенно академик М.Е. Массон (Ташкент).

Начало комплектования коллекций относится к маю 1963, когда под музей была отведена башня Кисловодской крепости. Кроме сбора экспонатов проводилась и другая разнообразная общественная деятельность (тематические встречи, вечера и т. п.). Городская археологическая секция краеведческого общества под руководством Н.Н. Михайлова активно формировала археологические коллекции для будущего музея. Открытие музея состоялось 9 мая 1965, в день 20-летия Победы. Первым директором стал И.Т. Тулинов.

В 1965-1970 успешно развивался как общественный музей. В первой экспозиции, построенной по тематическому (географическое положение, геология, природные особенности, археология, этнография, история) и хронологическому принципам, было выставлено всего около 600 экспонатов, существовали явные диспропорции и пробелы. Однако коллекции быстро накапливались, и в 1967 музею были выделены дополнительные помещения, отведен земельный участок, примыкающий к башне крепости. К 1969-1970 большой и разнообразный музейный материал превышал 10 тыс. единиц хранения. Уже в первые годы музей посещало до 50-60 тысяч горожан и гостей курорта ежегодно. Напряженная и разноплановая деятельность, широкие связи и контакты, участие в научных археологических экспедициях создали авторитет музею и обратили на него внимание Ставропольского государственного краеведческого музея им. Г.К. Праве.

В 1971-1975 музей был преобразован в филиал Ставропольского краеведческого музея. Первым заведующим филиалом стал Л.М. Мерцалов. В 1971-1972 создана новая экспозиция, сохранившая тематико-хронологический принцип построения, но исполненная на более высоком содержательном и художественном уровне. Сохранялись связи с активом Кисловодского краеведческого общества. В 1971 на базе музея создан Кисловодский отдел Географического общества СССР. К 10-летию музея в 1975 издан первый буклет о музее.

В 1976-1986 в качестве директора работал отставной офицер, участник войны, краевед Н.С. Вартанов. В число сотрудников вошли профессиональные историки, активизировал работу музейный совет. Важной заслугой было расширение экспозиционных площадей и создание постоянно действующей и периодически обновляемой выставки "Этнография и быт жителей Кисловодска XIX-начала ХХ в." Существенно выросло количество посетителей. Рекордный в истории музея показатель — 72350 человек достигнут в 1984. С 1977 музей приступил к самостоятельным археологическим исследованиям, в штате появился профессиональный археолог.

Вторая половина 1980-х-начало 90-х — этап работы музея в условиях подготовки к реставрации Кисловодской крепости. Масштабные реставрационные работы предполагалось провести в течение 1989-1990, но сложная обстановка в стране привела к значительному увеличению этих сроков. Заведующими работали Я.Б. Березин, Е.И. Зайцева, В.И. Дубров. Все экспозиции были демонтированы, музей временно переведен в помещения по ул. Жуковского, 12, где и был создан новый выставочно-фондовый комплекс (1989).

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

Современный этап развития музея начался в 1998, когда он стал самостоятельным муниципальным учреждением. Действующий директор музея С.С. Лузин, опираясь на поддержку Совета и Администрации Кисловодска, сумел наладить деятельность в новых условиях. С 1999 удалось возобновить федеральное финансирование и проведение реставрационных работ. В 2002 вступил в строй большой зал, площадью более 350 кв. м. Путем привлечения средств из различных источников изготовлены и установлены на воротах крепости мемориальные доски А.С. Пушкину и С.И. Уптону. Возле Крепости установлен памятный знак основания города, завершен монтаж казачьего креста-памятника, благоустроена прилегающая к музею территория и создан сквер 200-летия Кисловодска. Улучшилась материально-техническая база. Проводится активная выставочная, общественно-просветительская и культурно-массовая деятельность. Накануне 40-летия своего основания музей продолжает поступательное развитие, а музейный коллектив полон планов и творческих сил.