При правильной постановке работы ВМУО его штаты и структура были бы вполне достаточны для того, чтобы нести функции Генерального штаба флота в 1880 — начале 1890-х годов, когда численный состав боевых сил был мал, а при столкновении с «морскими державами» России пришлось бы ограничиться обороной отдельных пунктов побережья и посылкой крейсеров в океан с целью нарушения вражеского судоходства. Со временем, когда к началу XX в. русский флот вырос, перед ним встали более масштабные задачи. Теперь уже можно было говорить о борьбе на равных с флотами некоторых второстепенных морских держав, например Японии. Зимой 1901–1902 гг. в Николаевской Морской академии прошла стратегическая игра для Дальневосточного театра, причем посредники пришли к выводу, что неудачные для русской стороны действия объяснялись отсутствием плана войны. 20 ноября 1902 г. начальник ВМУО контр-адмирал Андрей Андреевич Вирениус представил тогдашнему начальнику ГМШ Зиновию Петровичу Рожественскому доклад о необходимости создания при ВМУО особого Оперативного отделения, основной задачей которого стала бы разработка плана войны, «который должен представлять собою ряд заблаговременных соображений и расчетов, обеспечивающих флоту быстрый переход с мирного положения на военное и определяющий, какую первую задачу (до первого столкновения) можно преследовать»[76]. А.А. Вирениус в 1902 г. замечал, что насущная необходимость службы Генерального штаба в русском флоте появилась не более пяти лет тому назад, примерно со времени занятия Порт-Артура, когда «ясно и определенно обозначились наши три вероятных и самостоятельных театра войны»[77]. Проект пошел по инстанциям и 29 ноября 1903 г. Государственный совет одобрил изменение структуры ВМУО, император утвердил это решение 2 февраля 1904 г., на седьмой день русско-японской войны[78]. Однако на практике разделение ВМУО на Распорядительно-учебную часть и Оперативное отделение произошло несколько раньше, в самом начале 1904 г. и вскоре Оперативное отделение стали именовать Стратегической частью. Не исключено, что дополнительным толчком для инициативы А.А. Вирениуса послужила реорганизация Главного Морского штаба французского Морского министерства. 31 января 1902 г. из ведения французского ГМШ были изъяты кадровые вопросы и офицеры, служащие в этом органе, смогли сосредоточиться исключительно на разработке военных планов[79].
Первым заведующим Стратегической частью стал капитан 1-го ранга Лев Александрович Брусилов (1857–1910). Он начал службу в 1875 г., поступив юнкером на Черноморский флот, где и прослужил без малого двадцать пять лет. С 1899 г. по февраль 1904 г. Л.А. Брусилов служил на Тихом океане, а в самом начале русско-японской войны получил назначение в Петербург. В течение шести месяцев он пытался оказывать влияние «из-под шпица»[80] на деятельность боевых сил флота, но, видя безуспешность этих попыток, перевелся в действующий флот командиром броненосного крейсера «Громобой»[81]. Впоследствии Л.А. Брусилов стал первым начальником вновь образованного МГШ.
В 1904 г. в составе ГМШ появилась Законодательная часть, которая должна была разрабатывать и докладывать в Адмиралтейств-совете законопроекты, касающиеся морского ведомства. Положение Законодательной части оказалось довольно сложным: с одной стороны, ее чиновники, имевшие основательную юридическую подготовку, могли грамотно составить законопроект, но в силу незнания специфики морской службы и нюансов военно-морского управления зачастую эти законопроекты оказывались бесполезными и даже вредными для практической деятельности флота. Несмотря на это, Законодательная часть и в период преобразований 1905–1914 гг. ревниво оберегала свою монополию на законотворческую деятельность, что приводило к трениям с другими подразделениями Морского министерства.