Музей истории рыбной промышленности Азово-Черноморского бассейна был создан Приказом № 217 Главного управления рыбной промышленности «Азчеррыба» 12 мая 1972 года. Директором Музея был назначен Александр Васильевич Буряченко, ветеран рыбной промышленности, первый начальник Севастопольского управления океанического рыболовства.

Под его руководством была разработана тематическая структура и тематико-экспозиционный план будущей музейной экспозиции, предпринято более 20 экспедиций по Азово-Черноморскому побережью для сбора экспонтов.

В первые годы существования Музей в виде музейной комнаты размещался в приспособленных помещениях. С февраля 1982 года разместился в двух залах Дворца культуры рыбаков, общей площадью 157 кв. м. Музей имеет 2 фондовых хранилища, методкабинет.

На 1 января 2014 года Музей располагал 2352 экспонатами. Непосредственно в музейной экспозиции представлено 985 экспонатов. За годы работы Музея экскурсии посетило свыше 110 тыс. человек.

В разработке первой музейной экспозиции вместе с А. В. Буряченко принимали участие зав. научно-методическим отделом Музея героической обороны и освобождения Севастополя, нынче известный краевед, В. Г. Шавшин, члены Союза художников Украины А. П. Шадрин и Ф. Д. Кутинов.

Постановлением Коллегии Министерства культуры УССР от 29.07.87 г.т Музею было присвоено звание «народный». Музей ведет большую просветительную работу, широко используя такие её формы как экскурсия, лекция, брейн-ринг, викторина, тематический вечер и др. Ежегодно организуется 5-6 новых выставок, тем самым расширяется возможность знакомства севастопольцев и гостей города с фондовой коллекцией Музея, совершенствуется действующая экспозиция.

В разные годы Музеем руководили Г. А. Майчук (1992-1998 г.г.), Н. А. Неврова (1999-2004 г.г.), внесшие значительный вклад в развитие всех видов работы . С13.01.2011 года Музеем заведует Т. Е. Тимофеева.

С 1996 года предприятия рыбной промышленности прекратили финансирование Музея. Он стал структурным подразделением Культурно-информационного Центра Министерства культуры Украины, сегодня функционирует в составе Культурно-информационного Центра г. Севастополя.

12 мая 2012 года в день празднования 40-летия Музея распоряжением Генерального директора Культурно-информационного Центра Т. В. Зениной №3-р Музею присвоено имя А. В. Буряченко.