Музей Севастопольской обороны, как он ранее назывался, создан по инициативе участников обороны 1854-1855 годов. Вначале располагался в доме генерал-адъютанта Э.И. Тотлебена, он находился напротив современного здания музея, не сохранился.
В пяти его комнатах размещалась экспозиция, открытие которой состоялось 14 сентября 1869 года. В 1895 году для музея построили специальное здание, его автор - академик архитектуры A.M. Кочетов.

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

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