Гернгросс получил приказ приступить к формированию стражи. Стоит заметить, что 46-летний полковник по своему боевому опыту как нельзя лучше подходил для такой роли. Отличившись на полях сражений Русско-турецкой войны 1877–1878 гг., Александр Алексеевич Гернгросс в течение целого года руководил в освобожденной Болгарии ликвидацией банд башибузуков, продолжавших терроризировать мирное население в Родопских горах. На службе в Закаспии, которая продолжалась с 1890 по 1897 г., офицеру также неоднократно приходилось преследовать шайки хищных туркмен…
Первые пять сотен Охранной стражи общей численностью 711 человек, набранные из казаков Терского, Кубанского и Оренбургского казачьих войск и усиленных батальонными солдатами, прибыли во Владивосток на пароходе Добровольного флота «Воронеж» уже 26 декабря того же года. 12 января 1898 г. первые сотни стражи вошли в город Нингуту.
Образцом организации Охранной стражи были войска Отдельного корпуса пограничной стражи (ОКПС). Начальник стражи приравнивался в правах к командиру бригады ОКПС, командиры сотен — к командирам отделов, их помощники — к командирам отрядов, урядники — к вахмистрам. Каждая сотня состояла из командира, 2 младших офицеров, вахмистра, 12 урядников, 2 трубачей, 120 казаков и ветеринарного фельдшера. Рядовой стражник был вооружен винтовкой и шашкой драгунского образца. Офицерам, вахмистрам и фельдшерам полагались револьверы.
В форменной одежде стражников присутствовал желтый цвет, намекающий на место службы. Желтыми были канты, выпушки, петлицы нижних чинов, суконные верхи черных казачьих папах и тульи фуражек. Стражников нарядили в черные тужурки и синие шаровары кавалерийского покроя. Черные петлицы офицерской формы украшались желтым кантом, пуговицей и эмблемой в виде скрещенных винтовки и шашки. Во избежание обвинений в использовании регулярной армии на территории суверенного соседа форма стражи не имела погон. Офицерам их заменяли золотые наплечные шнуры, а вахмистрам и урядникам — галуны на рукавах. Кокарды, петлицы и знамена стражи украшало изображение желтого китайского дракона, сразу же принятое в штыки казаками. Неприязнь станичников к «басурманскому змею» была столь велика, что форменные папахи они носили исключительно… кокардами назад.
Офицерский корпус стражи состоял из добровольцев — выходцев из армейских, казачьих и пограничных частей. При переводе в Охранную стражу офицеры сохраняли все права чинов действительной службы. Несмотря на то что офицеры-стражники считались «как бы вышедшими в отставку», они продолжали числиться в списках своих частей и имели право вернуться к старому месту службы. Служба в Охранной страже КВЖД приравнивалась к действительной, высоко оплачивалась и имела льготу по выслуге: два дня шли за три.
Очень быстро выяснилось, что имевшихся стражников для КВЖД недостаточно. В октябре 1897 г. началось формирование новых 10 сотен общей численностью 1390 человек (одна терская, две кубанских, три донских, три оренбурских и одна уральская). 17 мая 1898 г. на борту французского пароходе Les Alpes пополнение прибыло во Владивосток.
Плечом к плечу с казаками службу в рядах стражи несли солдаты, набранные в частях Дальнего Востока и составившие 8 рот общей численностью 2 тысячи штыков. Усиление стражи продолжалось, и по состоянию на 2 июня 1900 г. она состояла из 69 офицеров, 9 классных чинов, 3 священнослужителей и 4658 рядовых стражников.
Командование Охранной стражи располагалось в Харбине. Вся стража делилась на линии: Сунгарийскую (начальник — полковник П.Н. Денисов со штабом на станции Имяньпо), Аргунскую (начальник — полковник А.Ф. Зубковский со штабом на станции Фуляэрди) и Порт-Артур скую (начальник — полковник П.И. Мищенко со штабом на станции Телин). Протяженность сотенного участка линии доходила до 120 верст, а ротного — до 360 верст.