В тот же день, когда военно-полевой суд вынес Старку оправдательный приговор, Верховный Правитель адмирал Колчак произвел смотр командам 1-го и 3-го дивизионов Речного Боевого Флота. Он с удовлетворением отметил «отличный воинский вид этих частей, прошедших тяжелую службу на реках в течение прошлого года». Наверняка в эти дни и Колчаку, и Старку, да и вообще всем морским офицерам, волею судьбы и долга перед Родиной оказавшимся на просторах Сибири, будущее возрождение Флота казалось особенно близким. Колчак как никто другой понимал его значение для России, в том числе и в Гражданской войне. Было сформировано морское министерство, началось создание Речной боевой флотилии на Каме, организовывались морские части и учебные подразделения. Многим из тех, кто начал воевать на Волге в 1918 году, предстояло служить и воевать под Андреевским флагом вплоть до весны 1923-го.
Через два дня после вынесения контр-адмиралу Старку оправдательного приговора он прибыл в Омск. Именно ему предстояло возглавить новую воинскую часть, в которую вошли многие его сослуживцы по Речному Боевому Флоту Комуча – отдельную бригаду морских стрелков. Приказом по Флоту и морскому ведомству, подписанным 3 декабря 1918 года еще одним сослуживцем Старка по Минной дивизии – адмиралом М. И. Смирновым, возглавившим морское министерство в правительстве адмирала Колчака, Георгию Карловичу было поручено возглавить комиссию «для составления проекта штата и положения Морской Стрелковой бригады и отдельных береговых команд Морского Ведомства и выяснения вопросов, связанных с предстоящим формированием частей морских стрелков».
12 декабря Верховным Правителем России и Верховным Главнокомандующим всеми сухопутными и морскими силами адмиралом Колчаком был издан приказ, который гласил: «1. Из команд Речной Боевой флотилии сформировать в составе Морведа [152] стрелковую бригаду шестибатальонного состава – “Отдельную бригаду Морских стрелков”. 2. Формирование производить последовательно, начиная со штаба бригады и двух батальонов и произвести дальнейшее формирование после обучения двух батальонов, причем порядок формирования должен быть таков, чтобы части были постоянно боеспособны. 3. Снабжение и пополнение команд Речной Боевой флотилии до состава двух батальонов Морских стрелков произвести из Военведа [153] . 4. Предоставить командиру Отдельной бригады Морских стрелков права начальника дивизии». Согласно штатам, при каждом батальоне должны были быть следующие части: специальная рота, пулеметная команда, команда связи, подрывная команда, перевязочный пункт, нестроевая команда, учебная команда. Всего в бригаде предполагалось иметь 75 офицеров, 8 военных чиновников, 1 496 солдат и 207 лошадей. Командиром бригады был назначен контр-адмирал Г. К. Старк, помощником командира – капитан 2-го ранга П. В. Тихменев.
К 23 марта 1919 года в бригаде были укомплектованы два батальона и команда связи Штаба, сформированные в Красноярске. В первом батальоне по спискам числилось 1 050 человек, во втором – 521, а всего в бригаде – 1 637 человек рядового и унтер-офицерского состава, из них 236 добровольцев, остальные – мобилизованные. Причем заявления с просьбой о зачислении в бригаду подавали самые разные люди, от офицеров Флота до учеников Учительской семинарии и гимназистов. Из списков личного состава видно, что бригада была морской лишь по подчиненности Морскому министерству и названию. Моряки занимали в ней только штабные и командные должности, вплоть до уровня ротного командира. Основную же массу командиров составляли сухопутные офицеры разных родов оружия. Постановлением Совета министров Всероссийского Правительства от 10 января 1919 года был учрежден Корпус морских стрелков. В соответствии с «Временным положением об офицерах Корпуса Морских стрелков» офицеры сухопутных войск при поступлении в части морских стрелков переименовывались в морские чины.
Третий и четвертый батальоны бригады были сформированы в апреле – мае 1919 года. Местом формирования третьего батальона была назначена Пермь, четвертого – Уфа. С 23 декабря 1918 года по 14 марта 1919-го в составе бригады находился бронепоезд, вооруженный одним 75-мм и тремя морскими 3-дюймовыми орудиями (затем он был передан Военному ведомству, но без личного состава, орудий и боезапаса). Стрелковое оружие для двух батальонов бригады было выделено союзниками-французами, но вместо 1 700 винтовок бригада получила 1 660, из них много учебных и сломанных. Первоначально организация бригады предусматривала тесное взаимодействие ее с Речной боевой флотилией, сформированной из вооруженных пароходов для действий на Каме, даже размещение части обоза на плавсредствах, но в действительности бригада действовала как самостоятельная сухопутная часть, лишь время от времени – совместно с флотилией.