3 февраля 1958 года 31-я ДиТКА была преобразована в 41-ю бригаду ТКА.
В 1959 – 1960 годах в бригаду прибыли первые в мире серийные ракетные катера и прошли их испытания. Первые ракетные стрельбы.

1 июля 1960 года 344-й дивизион торпедных катеров был расформирован, а торпедные катера были переданы в состав 295-го ДТКА.

В 1961 году в бригаду поступили новые катера проектов «205» и «206».

15 октября 1961 года был сформирован 349-й дивизион торпедных катеров в составе 11 ТКА, исключенных из состава 296-го ДТКа, который был пере-формирован в 296-й дивизион ракетных катеров.

30 октября 1961 года 41-я БТКА была преобразована в 41-ю бригаду ракет-ных катеров (РКА).
В 1962 году четыре катера бригады были перебазированы на Кубу для уча-стия в секретной операции «Анадырь».

29 июля 1966 года 349-й дивизион торпедных катеров был переформиро-ван в 349-й дивизион ракетных катеров в составе четырех ракетных катеров. 296-й дивизион ракетных катеров в составе шести РКА был передислоцирован из Севастополя в п. Черноморское с подчинением командиру 41-й ОБРКа, там же была сформирована береговая база дивизиона надводных кораблей с подчи-нением командиру 296-го дивизиона.

В 1969 году в часть прибыл для испытаний артиллерийский катер «АКА-225».

В сентябре 1969 года в соединении был сформирован 73-й дивизион кате-ров резерва с подчинением командиру бригады.

В 1970 году были приняты от промышленности первые малые ракетные корабли «МРК-3» и «МРК-7» («Буря» и «Бриз»).

5 июля 1971 года было сформировано управление 166-го Новороссийского Краснознаменного дивизиона малых ракетных кораблей, а 14 августа 1971 года малые ракетные корабли МРК «Буря» и «Бриз» подчинены командиру 166-го ДНМРК.

В 1972 году был принят от промышленности первый торпедный катер про-екта «206М». Катера и корабли соединения начали регулярные выходы на бое-вую службу в Средиземное море.

1 июля 1974 года 73-й дивизион катеров резерва был переименован в 73-й дивизион ракетных и торпедных катеров.

14 июня 1976 года 296-й Констанцский дивизион ракетных катеров пере-именован в 296-й отдельный Констанцский дивизион ракетных катеров. В июле 1976 года 296-й ОДРКа исключен из состава 41-й ОБРКа и передан в состав Крымской ВМБ.

В 1978 году в бригаду поступают первые РКА проекта «206МР».
В 1979 году в соединение прибыл первый МРК на подводных крыльях проекта «1240».

11 марта 1980 года 295-й Сулинский Краснознаменный дивизион торпед-ных катеров расформирован и на его основе создан 295-й Сулинский Красно-знаменный дивизион малых ракетных кораблей в составе:
МРК «Буря»;
МРК «Гроза»;
МРК-5;
ПД-26;
ПД-19.

В 1981 году в бригаду прибыл катер «Р-46» типа «Молния».
В 1987 году в бригаду прибыл первый МРК на воздушной подушке – «МРК-27» («Бора») проекта «1239».

В феврале 1990 года был расформирован 73-й дивизион ракетных и тор-педных катеров. 295-й дивизион малых ракетных кораблей был переименован в 295-й Сулинский Краснознаменный дивизион ракетных катеров.

В ноябре 1992 года был расформирован 349-й дивизион ракетных катеров, а катера и экипажи переданы в состав 295-го дивизиона ракетных катеров.

12 июня 1997 года на кораблях и катерах бригады подняты исторические Андреевские флаги ВМФ РФ.

В июле – августе 1997 года ракетные катера «Р-15» пр. 206МР, «Р-63», «Р-54» пр. 1241 и плавбаза «ПРТБ-13» переданы в состав ВМС Украины.

25 июля 2002 года в состав бригады вошел ракетный корабль на воздушной подушке «Самум» проекта «1239».
В 2002 году по результатам учений корабельная ударная группировка 295-го ДНРКА (командир капитан 2 ранга Ю.С. Земский) заняла 1-е место в Воен-но-Морском флоте по уничтожению кораблей противника.
В 2003 году весенний сбор-поход кораблей ЧФ с участием ракетных ко-раблей бригады.

В состав бригады входят:
166-й Новороссийский Краснознаменный дивизион ракетных кораблей:
РКВП «Бора»;
РКВП «Самум»;
МРК «Зарница» (на ремонте в Севастополе, выход из ремонта – 2004 г.);
МРК «Штиль» (до 1992 года «Комсомолец Мордовии»);
МРК «Мираж».

295-й Сулинский Краснознаменный дивизион ракетных катеров:
РКА «Р-44»;
РКА «Р-60»;
РКА «Р-239»;
РКА «Р-109»;
РКА «Р-71»;
РКА «Ивановец».

узел связи;
учебные кабинеты;
береговая база.