30 січня 1890 року на засіданні єпархіального історико-статистичного комітету затвердили правила церковного давньосховища - музею старожитностей.
На цьому ж засіданні секретарем давньосховища було обрано Ю.Й.Сіцинського, а завідуючим В.С.Якубовича.
Спочатку цей музей складався із трьох відділів:
1. Бібліотека, яка формувалась із книг історії Поділля, твори польських, російських та місцевих авторів.
2. Архів, основа якого складалась із докуменів минулого і візитів церков.
3. Фондосховище, де зберігалися стародруки XVI-XVIII століть, гравюри, фото, пам'ятки мови і письма, скульптура, посуд, живопис й інші цікаві предмети.
Завдяки активному процесу збирання етнографічних, іторичних, фольклорних пам'яток, стародруків різних епох, працівникам давньосховища вдалось створити перші каталоги колекцій: «Опись предметов старины» том І - 1904 року і том ІІ - 1909 року. Найбільшу роботу по створенню Кам'янець-Подільського музею зробив Сіцинський Ю.Й., його роботи й сьогодні - бібліографічна рідкість. Робота Ю.Й.Сіцинського по збору експонатів й публікації матеріалів стала основою для створення історичного музею-заповідника.
1912 року в Петербурзькому інституті цивільних інженерів розроблено проект нового будинку для музею. Був складений кошторис на суму 25 тис. крб., виділена земельна ділянка біля собору Олександра-Невського. Здійснення цих планів перешкодила перша світова війна: перша і друга евакуації музею з Кам’янця у м. Вінницю, пізніше в Немирів 1914 рік, в червні 1917 року - третя евакуація музею в м. Вінницю.
1924 року музей переїхав з будинку колишнього духовного училища в будинок чоловічої гімназії (тепер історичний факультет Національного університету). Три музеї були об’єднанні в один центральний.
23 березня 1928р. постановою РНК УРСР оголошено замок-фортецю в м.Кам’янці-Подільському Державним історико-культурним заповідником.
У вересні 1929 року історико-археологічний музей реорганізується в краєвий і переходить в нові приміщення – будинок робітників освіти (тепер будівельний технікум) і в будинок по вул. Соборній (колишня 7-ма школа). Музею передано Петропавлівський кафедральний костьол в травні 1936 року. Були створені наступні відділи: 1) зоології; 2) геології; 3) палеонтології; 4)антирелігійний. А вже в 1937 році історичний музей переміщений на територію фортеці-заповідника.
1 липня 1946 року рішенням Ради Міністрів УРСР музею надали статус республіканського.
1949 року директором музею призначено Г.М.Хотюна.
1967 року музею передано будинок Ратуші, пам’ятка архітектури 16-18 ст.
3 лютого 1982 року в будинку колишньої духовної семінарії відкрито художній відділ музею.
1984 року музею передано верхній поверх Вірменського торгово будинку 16-18 ст., де розміщено канцелярію і бібліотеку музею. Директором музею призначено С.Е.Баженову.
1997 року фонди музею-заповідника перевезено у нові відреставровані приміщення. Директором музею призначено Л.П. Станіславську.
Після капітального ремонту 1999 року в пам’ятці архітектури 18-19 ст. створено нову експозицію художнього відділу музею. Розпочато великий обсяг реставраційних робіт у баштах і підземеллях фортеці.
2001 року у залах колишнього Вірменського торгового будинку, пам’ятці архітектури 16-17 ст. побудована експозиція відділу археології.
2006 році після проведення ремонту на 2-му поверсі Ратуші, музеєм відтворено інтер’єр середньовічних залів засідань.
У залах Ратуші музеєм побудовані експозиції відділів: «Історія грошового обігу на Поділлі», «Історія Магдебурзького права та самоврядування на Поділлі». Музейні працівники розпочали проведення нічних екскурсій у фортеці.
У 2008 році рішенням міськвиконкому, музею передано приміщення Вірменської криниці – пам’ятки архітектури ХVІІ ст.
2011 року директором музею призначено В.С.Травінського.
В травні 2012 року міська рада передала на баланс історичного музею-заповідника приміщення Туристично-Інформаційного Центру та виставкової зали.
2016 року директором музею призначено О.О. Зарембу.