Первым флотским сухопутным формированием, созданным на Востоке России, стала харбинская Морская рота имени адмирала Колчака, сформированная в мае 1918 г. В дальнейшем на ее основе был развернут Отдельный батальон морских стрелков Дальнего Востока при Амурской флотилии. Этот батальон базировался на Владивосток и в боевых операциях участия не принимал. 12 декабря 1918 г. верховный правитель России и верховный главнокомандующий всеми сухопутными и морскими силами России адмирал Колчак издал приказ № 73: «
12 декабря 1918 г. приказом управляющего Морским министерством контр-адмирала М.И. Смирнова № 29 для бригады была установлена форма одежды защитного цвета, по образцу пехотных частей, но с рядом отличий. Так, на левом рукаве носился вышитый якорь синего цвета. Офицеры носили погоны флотского образца с вышитыми литерами «М.С.» приборного цвета с накладной медной арматурой, изображающей либо две скрещенные винтовки (для офицеров морских стрелков), либо две скрещенные пушки (для офицеров морских стрелков — артиллеристов). Унтер-офицеры и рядовые должны были носить на погонах черные буквы «М.С.». Офицерам полагалось носить оружие флотского образца (т. е. кортик), но допускалось ношение и шашек. 1 февраля 1919 г. приказом за № 45 унтер-офицерам и рядовым присвоили черные погоны с литерами «М.С.» и желтой арматурой.
К 23 марта 1919 г. в бригаде удалось укомплектовать два батальона и команду связи штаба бригады, сформированные в Красноярске. В первом батальоне по спискам числилось 1050 человек, во втором — 521. Всего по спискам в бригаде числилось 1637 человек рядового и унтер-офицерского состава, из них 236 добровольцев, остальные — мобилизованные. Состав добровольцев оказался достаточно пестрым: заявления с просьбой о зачислении в бригаду подавали самые разные люди — от офицеров флота до учеников учительской семинарии и гимназистов включительно.
Из списков личного состава видно, что бригада являлась морской только по названию и подчиненности Морскому министерству. Моряки занимали в ней только штабные и командные должности, вплоть до уровня ротного командира. Основную массу командиров составляли сухопутные офицеры разных родов оружия. Окончательно положение сухопутных офицеров в бригаде было оформлено постановлением Совета министров Всероссийского правительства Колчака № 85 от 10 января 1919 г. Был учрежден Корпус морских стрелков. В соответствии с «Временным положением об офицерах Корпуса Морских стрелков», офицеры сухопутных войск при поступлении в части морских стрелков переименовывались в морские чины.
Третий и четвертый батальоны бригады сформировались в апреле — мае 1919 г. Местом формирования третьего батальона назначалась Пермь, четвертого — Уфа.
С 23 декабря 1918 г. по 14 марта 1919 г. в составе бригады находился бронепоезд, вооруженный одним 75-мм и тремя морскими трехдюймовыми (так они называются в документах; возможно, речь идет о сухопутных «трехдюймовках» на морских станках) орудиями. Бронепоездом командовал капитан 2-го ранга П.П. Феодосьев, которою впоследствии сменил лейтенант Н.Н. Гакен. 14 марта бронепоезд передали Военному ведомству (без личного состава, орудий и боезапаса).