Батальон, организованный в конце мая 1942 года в Москве, в товарных составах был переброшен в Ейск и оттуда провел шесть походов через Азовское море на побережье между Мариуполем и Таганрогом, занятое немецкой армией. Всякий раз моряки, высадившись на берег, уничтожали гарнизоны противника, захватывали пленных.
7 августа капитан-лейтенант Востриков атаковал станицу Широганскую. С флангов ее охватили основные силы батальона, а в тыл были заброшены мелкие группы автоматчиков. Востриков опередил врага. В ночном бою станицу освободили, полностью уничтожили вражеский гарнизон, оказавший сопротивление, взяли трофеи.
В рукопашной схватке отличились автоматчики Василий Яшин, Олег Минин, Панна Козлова, Валерий Лебединский. Нелегко им было удерживать позиции ради тех, которых они даже в глаза не видели, помогая им отойти. Слава батальона росла, а вместе с ней росла и его численность: со всех сторон приходили туда моряки.
На следующий день, получив приказ, батальон отошел через Ясенскую и Морозовскую переправы на Ахтари, а оттуда морем отплыл на кораблях в Темрюк. У разбитой бомбами Морозовской переправы моряки, скрепя сердце, сожгли свои потрепанные грузовики.
После кровопролитных боев с численно превосходящим противником, отбивая многочисленные атаки пехоты, кавалерии и танков, батальон оставил горящий, затянутый дымом город Темрюк.
Капитан-лейтенанту Вострикову приказали: любой ценой, хотя бы на сутки, сдержать наступающего врага в районе хутора Адагум и станицы Варениковской. Бойцы батальона окопались и заняли оборону. На рассвете 25 августа фашистская пехота, поддержанная дюжиной танков, начала наступление. Моряки без единого выстрела близко подпустили врага и с криком «полундра» поднялись в контратаку. Почти еще мальчик, младший лейтенант Федорович с двенадцатью матросами зашел в тыл 118-у немецкому батальону СС. Заметавшихся фашистов расстреливали из автоматов, забрасывали гранатами. Трупы их валялись на поле боя, среди пылающих копен пшеницы.
Федорович рассказывал потом, как в этом бою раненые краснофлотцы Смирнов и Павлов, не раздумывая, обвязавшись гранатами, бросились под гусеницы шедших на них двух танков и не пропустили их. Героическая смерть товарищей потрясла и вдохновила бойцов батальона. Четыре танка они подбили из противотанковых ружей, уничтожили около двухсот солдат и офицеров, обратили в бегство два эскадрона кавалерии противника. В этом бою моряки опрокинули общеизвестные дотоле мерила человеческой выносливости.
Вражеские самолеты летали над головами матросов, но, не имея достаточно бомб, сбрасывали рельсы, пустые железные бочки.
В это время 15-й и 16-й батальоны Новороссийской военно-морской базы свели в 1-й морской полк Черноморского флота. В звездную ночь на 26 августа 1942 года 16-й батальон, которым командовал майор заслуженный мастер спорта Дмитрий Красников, из Туапсе на эсминце «Сообразительный» прибыл в Новороссийск.
Красникова еще при обороне Севастополя знали как человека несгибаемой воли, личной храбрости и физической выносливости. Он сразу бросил в бой батальон против наступающих частей 79-й немецкой дивизии. Движение фашистов застопорилось, но вскоре на помощь им подошла 101-я румынская дивизия с приданными ей частями 13-й танковой дивизии.
Батальон майора Красникова прикрывал отход частей, разрозненных с основными силами у Краснодара, которые по шоссе Новороссийск — Туапсе и дальше Туапсе — Майкоп, через Шаумян, выдвигались в район Хадыженских нефтепромыслов.
К тому времени в Новороссийской бухте, у каменных пирсов элеваторной пристани, лег на дно легендарный лидер «Ташкент», потопленный вражеской авиацией при звездном налете. Матросы с лидера, оставшиеся в живых, стиснув зубы, ушли в сводный морской полк, где встретились с моряками гвардейских крейсеров «Красный Кавказ» и «Красный Крым», линкора «Парижская коммуна», подводных лодок, торпедных катеров и береговой обороны. Там оказалось много орденоносцев, защищавших Одессу и Севастополь, Москву и Ленинград, — людей, умевших ценить жизнь, знающих, что такое война, что такое фашист. На белесых холмах у города Новороссийска моряки под командованием подполковника Максима Кравченко приняли на себя первые удары.
6 сентября полк переименовали в морскую бригаду и слили с 305-м и 144-м морскими батальонами. С этого дня началась героическая история бригады — защита Новороссийска. Она прикрывала дороги главного направления. На карте в эти дороги, словно занозы, втыкались синие стрелы немецкого наступления, и при взгляде на нее казалось, что все действия бригады похожи на жертвоприношение, ибо она обречена.