В Севастополе, 26 сентября 1869 года состоялось открытие музея истории Черноморского флота России. Он появился на улице Екатерининской в доме одного из руководителей первой обороны города генерала Эдуарда Тотлебена. Комитет по сбору средств на открытие музея возглавлял редактор военной газеты «Русский инвалид», генерал-лейтенант Петр Меньков.

Российский император Александр II 1 декабря 1869 года издал указ о передаче Севастопольскому музею имения в деревне Эмир Таврической губернии Бердянского уезда площадью 1 936 десятин. Патроном музея и находившихся в его ведении благотворительных учреждений стал великий князь Александр Михайлович. При музее в 1874 года были построены приют для инвалидов, школа на 40 учеников, Ксеньинская церковно-приходская школа на 300 учащихся, школа соломоплетения для девочек.

Строительство нового здания для музея по проекту академика Александра Кочетова, было начато 28 июня 1892 года и завершилось 5 октября 1895 года. Было затрачено 150 тысяч рублей, из них 100 тысяч затратили морские и военные ведомства, причем последнее выделило также и участок под его постройку. Здание было выполнено в строгом классическом стиле, с чугунными и бронзовыми украшениями.

На главном фасаде был изображен «севастопольский знак»: крест и число 349, означающее количество дней обороны. Боковые фасады были украшены чугунными арматурами, изображающими части парусных кораблей, пушки, прикрытые бронзовыми знаменами. Украшения фасадов и интерьера были выполнены по проекту одесского скульптора Бориса Эдуардса. Ежегодно музей посещают около 80 тысяч человек.

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

По каталогу 1913 года в музее уже насчитывалось свыше двух тысяч экспонатов, в середине 2000-х годов - свыше 30 тысяч экспонатов. В период второй обороны Севастополя музей продолжал работать и пополняться экспонатами, которые приносили защитники города. Часть наиболее ценных экспонатов была эвакуирована в Баку, затем в Ульяновск.

Оставленная часть экспозиции из-за того, что здание музея было частично разрушено, была переведена в здание картинной галереи. После освобождения Севастополя от фашистов здание было восстановлено, и 15 августа 1948 года музей возобновил выставочную деятельность.