Формирование наследует награды, боевую славу и звания 126-й стрелковой дивизии (2-го формирования) принимавшей участие в Великой Отечественной войне. Дивизия принимала участие в освобождении полуострова Крым в 1944 году. В 1960—1980 годах дивизия входила в состав 32-го Кенигсбергского армейского корпусаОдесского военного округа.
В 2003 году на базе частей 32-го армейского корпуса была сформирована 36-я отдельная бригада береговой обороны Военно-морских сил Украины, в/ч А2320. Она после трёхнедельной блокады гарнизона силами самообороны Крыма и «вежливыми людьми» во время аннексии Крыма Россией 21 марта 2014 вместе с её командиром полковником С. И. Стороженко вошла в состав Вооружённых Сил РФ как отдельная бригада береговой обороны Черноморского флота[6]. Незначительное количество верных присяге Украины военнослужащих убыло на территорию материка. По данным С. И. Стороженко из 1200 военнослужащих убыло 199, уволилось 300, остальные присягнули РФ[6]. 1 декабря 2014 года на базе этого соединения была сформирована 126-я отдельная бригада береговой обороны[7].
11 декабря 2014 года бригада получила боевое знамя из рук адмирала Александра Витко[1]. 21 октября 2016 года строительство инфраструктуры бригады было завершено[2][8]. В 126-й обрбо две трети личного состава — военнослужащие-контрактники, а все подразделения постоянной готовности полностью укомплектованы военнослужащими по контракту[9]. Численность бригады насчитывает около 2000 человек личного состава[2].
Войска бригады на параде 22-го корпуса к 75-летию Победы в 2020 году в Симферополе
