67 бригада ОВР была образована 19.09.1962 г. на основании Директивы ГК ВМФ СССР. В соединение входили: 58-й дивизион противолодочных кораблей (8 МПК), 44-й дивизион тральщиков (8 МТЩ), катер связи, 2 бонно-сетевые партии, пост НиС в Западной Лице.
Первым командиром бригады стал Герой Советского Союза капитан 1 ранга Завгородний Александр Аврамович (сентябрь 1962 г. - январь 1965 г.).
10.11.1962 г. корабли бригады были перебазированы из Полярного в губу Ура.
Август 1963 г. - соединение было перебазировано из губы Ура в Ара-губу.
1964 г. - сформированы два поста наблюдения и связи в Ура-губе и 103-й пост НиС в Ара-губе с подчинением их бригаде.
Декабрь 1966 г. - в состав бригады вошла береговая батарея противолодочной обороны на мысе Выев-Наволок.
1968 г. - противолодочный дивизион произвел замену старых МПК проекта 122 бис на МПК проекта 204.
декабрь 1969 г. - бригада перебазирована из Ара-губы в пос. Порт-Владимир (о. Шалим).
1988 г. - произведена замена МПК проекта 204 на МПК проекта 1124.
1.09.1993 г. - бригада перебазирована на новое место дислокации в Оленью Губу. В тот же период вошел в состав бригады и был перебазирован из Полярного 270-й гвардейский Печенгский Краснознаменный противолодочный дивизион.
1.10.1994 г. - в состав бригады вошли МПК-10, МПК-33 и МПК "Юнга" из расформированного 141-го отдельного дивизиона кораблей ОВР из Лиинахамари.
Июль 1995 года - в состав бригады вошли МПК-142, МПК-14, МПК-194, БТ-15 и БТ-109 из расформированной 2-й бригады кораблей ОВР из Гремихи.