Флот создан 24 декабря 1955 г. в результате объединения 4-го и 8-го ВМФ. ОО создан в начале 1956 г.

С 1984 г. флот находился в подчинении Главного командования войск Западного направления (см. УОО КГБ).

Начальники:
1. КЛИМЕНКО Иван Исаевич (20 февраля – 16 октября 1956 г.), полковник;
2. МОЗГОВ Николай Кириллович (1956 – 1962 г.), полковник, с 18 февраля 1958 г. – генерал-майор;
3. РОДИН Александр Петрович (апрель 1962 – 1963 г.)
4. ТИМОФЕЕВ Андрей Иванович (15 апреля 1963 – 20 марта 1965 г.), полковник, с 9 июля 1963 г. – капитан 1-го ранга, с 10 декабря 1964 г. – контр-адмирал;
5. ТИХОНОВ Александр Михайлович (1965 – 1972 г.), капитан 1-го ранга, контр-адмирал;
6. НЕРУШЕНКО Александр Николаевич (17 мая 1972 – 12 января 1981 г.), контр-адмирал;
7. ВЕТОШКИН Юрий Иванович (12 января 1981 – 4 июля 1989 г.), капитан 1-го ранга, с 17 февраля 1982 г. – контр-адмирал;
8. ДРАЧЕНКО Анатолий Павлович (1989 – 1991 г.), капитан 1-го ранга;

И.И.Клименко	Н.К.Мозгов	А.П.Родин	А.И.Тимофеев
А.М.Тихонов	А.Н.Нерушенко	Ю.И.Ветошкин	А.П.Драченко

Заместители начальника:
ТИМОФЕЕВ Андрей Иванович (26 марта 1956 – 15 апреля 1963 г.), полковник;
ЖАРДЕЦКИЙ Александр Владиславович (октябрь 1971 – март 1975 г.)

А.И.Тимофеев	А.В.Жардецкий

Подчиненные органы:

• ОО КГБ по 14-й эскадре ПЛ (с 1976 г.)
• ОО КГБ по Восточно-Балтийской флотилии (до 1960 г.)
• ОО КГБ по авиации флота (с 1980 г. – ВВС флота)