Аппарат трех первых округов создавался постепенно и во многом носил характер экспериментального. Первоначально в Виленском и Киевском округах были созданы только военно-окружные штабы с временными штатами, в Варшавском же округе продолжали существовать все отделы полевого управления бывшей 1-й армии. Снабжение войск округов производилось прежними хозяйственными учреждениями. Но уже в конце 1862 г. созданы окружные интендантства (по образцу провиантских комиссий Оренбургского и Сибирского отдельных корпусов), ведавшие, однако, снабжением войск в округах только продовольствием, вещевое же их довольствие до августа 1864 г. (до момента принятия Положения о военно-окружных управлениях) производилось комиссариатскими органами Военного министерства.
В ноябре 1862 г. Д.А. Милютин предложил создать на западе империи и четвертый приграничный военный округ – Одесский – на территории Новороссийского края, охватывавшего Екатеринославскую, Херсонскую и Таврическую губернии, а также Бессарабской области. Это предложение диктовалось несколькими обстоятельствами. Во-первых, необходимостью продолжения военно-окружной реформы. Во-вторых, территории указанных регионов, как и первые три округа, также примыкали к западным границам России, и в случае конфликта с Австрией, которая неодобрительно смотрела на меры России по подавлению Польского восстания, Одесский округ мог бы сыграть роль ближайшего к театру военных действий воинского формирования (как это было впоследствии во время Русско-турецкой войны 1877–1878 гг.). В-третьих, дислоцированный на территории Новороссийского края 5-й армейский корпус входил ранее в состав 1-й армии, в связи с упразднением которой ему надлежало придать новое административное положение. Так же как в Виленском и Киевском округах, военный министр предложил «впредь до повсеместного преобразования военного управления в государстве» непосредственно подчинить командующему нового округа только полевые войска, в частности 5-й армейский корпус, части Сводного кавалерийского корпуса (при этом их корпусная организация заменялась дивизионной) и более мелкие полевые формирования, дислоцированные в крае. Все другие категории войск (резервные батальоны, внутренняя стража, крепостная артиллерия, местные инженерные части и др.), по примеру Виленского и Киевского округов, должны были временно оставаться в ведении своих прежних начальников.
Аппарат нового военного округа планировалось формировать из кадров упраздняемых в связи с созданием округа штабов 5-го армейского и Сводного кавалерийского корпусов и управлений (дежурств) Новороссийского и Бессарабского генерал-губернаторств. В Одесском военном округе первоначально не предполагалось создавать окружное интендантское управление, оставив издавна существовавшую в Новороссии систему довольствия войск через хозяйственные учреждения центрального подчинения, но с учреждением должности окружного интенданта.
Возникли трудности в связи с включением в состав Одесского округа двух артиллерийских дивизий, находившихся в непосредственном подчинении по командной части у генерал – фельдцейхмейстера (великого князя Михаила Николаевича). По вопросу нового порядка подчиненности этих дивизий Д.А. Милютин обратился к самому великому князю Михаилу Николаевичу, но проблема так и не была окончательно решена. Много хлопот вызвало упразднение Сводного кавалерийского корпуса, части которого находились не только в Новороссии, но и в Курской, Харьковской и других губерниях; его командиром был один из самых решительных противников военно-окружной реформы генерал от кавалерии И.П. Оффенберг. После длительной переписки удалось добиться решения о расформировании корпуса, барон Оффенберг получил назначение на должность члена Военного совета министерства.