Dès 1822, des géologues et des botanistes constituent un « cabinet public » d’histoire naturelle, présenté au sein du collège Buvignier. Par la suite, les collections sont transportées à la Sous-Préfecture puis à l’Hôtel de Ville où un musée est ouvert en 1874.

Une grande partie du fonds d’histoire naturelle, particulièrement fragile, a alors en partie disparu en raison des déménagements successifs des collections et de la guerre de 1870, mais les dons et legs se multiplient pour enrichir les collections.

Le fonds d’archéologie locale se développe notablement, notamment grâce à l’action de Félix Liénard, conservateur du musée entre 1853 et 1894. Dans la seconde moitié du XIXe siècle, les collections de Beaux-arts deviennent plus importantes et s’enrichissent des dépôts de L’État.

En septembre 1894, un incendie ravage l’Hôtel de Ville. Toutes les collections présentées sont touchées et les pertes sont considérables. Néanmoins, le bâtiment est restauré, et le musée ouvre à nouveau ses portes en 1905. Sept ans plus tard, en 1912, le musée quitte l’Hôtel de Ville et gagne le Palais Épiscopal alors désaffecté suite à la loi de séparation des Eglises et de l’Etat. L’inauguration a lieu le 25 mai 1913. L’année suivante, les débuts de la Première Guerre mondiale entraînent l’évacuation d’une grande partie des collections à Bar-le-Duc, dans les environs de Vaucouleurs et dans le Puy-de-Dôme. Le fonds d’histoire naturelle, resté à Verdun, est alors entièrement détruit.

Au lendemain de la Guerre, la Ville de Verdun décide en 1920 d’acheter l’hôtel de la Princerie pour y installer durablement le musée. Ce bâtiment Renaissance, très endommagé par les bombardements, est profondément restauré, et le musée est inauguré en 1932.