Музей является одним из старейших в стране. Основан 13 (25) мая 1811 г. градоначальником С. М. Броневским как Музей древности. Первоначально располагался в средневековой мечети. В 1871 г. занял здание, построенное по проекту И. К. Айвазовского, а в 1925 г. перешел в дом самого художника. После революции именуется вначале археологическим, а с середины 30-х гг. – краеведческим музеем. В годы Великой Отечественной войны коллекции музея были частично эвакуированы, частично разграблены оккупантами. В 1945 г. музей возобновил работу. С 1987 г. размещается в здании, построенном во второй половине XIX в. в традициях архитектуры классицизма.
Формирование музейного собрания древностей началось в первом десятилетии XIX в. До настоящего времени это наиболее значительная часть музейных фондов. В его составе было 12 тыс. предметов, в том числе уникальные античные и средневековые эпиграфические памятники, археологические комплексы из раскопок Феодосии и других древних городов и поселений юго-восточного Крыма. В XX в. фонды музея пополняются этнографическими и документальными материалами, связанными с историей Феодосии XIX – начала XX вв. С конца 20-х гг. формируются собрания по истории Феодосии в новейшее время, включившие поздние материалы о борьбе за установление советской власти в Крыму, а также значительный фонд экспонатов и документов, посвященных подвигу советского народа в Великой Отечественной войне. С середины 20-х гг. создаются природоведческие коллекции минералов, окаменелостей и обширный гербарий. Более 5 тыс. монет входят в нумизматическую коллекцию. Богата научная библиотека (более 11 тыс. томов), имеющая редкие издания XVIII – XIX вв. Всего музейные фонды содержат более 60 тыс. экспонатов, среди них много уникальных.
Экспозиция музея состоит из трех отделов – природы, дореволюционного, советского.
Есть в экспозиции раздел, посвященный послевоенному восстановлению и развитию народного хозяйства. Экспонаты заключительных залов ведут речь о современной Феодосии. Экспозиция здесь мобильная, отражающая экономическое развитие города. Представлены образцы промышленной продукции, производимой в Феодосии и известной далеко за ее пределами. При музее действует клуб интересных встреч «Кругозор». Ежегодно проводятся выставки фондовых коллекций.
