Коцебу был официально назначен на должность Новороссийского и Бессарабского генерал-губернатора в декабре 1862 года, когда она уже утратила былой блеск. Через 2 дня после этого события (25 декабря) был учреждён Одесский военный округ и Коцебу принял на себя командование им.

Военно-окружная система вводилась в рамках армейских реформ Дмитрия Милютина. Своей целью это преобразование имело улучшение управляемости войск и децентрализацию системы контроля над армейскими структурами. Создание первых четырёх округов (Виленского, Варшавского, Киевского и Одесского) произошло в августе–декабре 1862 года как своеобразный эксперимент на основе временного положения.

Три из четырёх первых командующих округами являлись одновременно главами соответствующих генерал-губернаторств (в Прибалтике, Малороссии и Новороссии). Будучи кадровым военным Коцебу рассматривался в Петербурге как компетентный и энергичный реализатор военно-окружной реформы, достойный военный руководитель на важнейшем Балканском направлении.

Это первоначальное совмещение гражданской и военно-административных должностей определило территорию ответственности Одесского военного округа (Херсонская, Таврическая, Екатеринославская губернии и Бессарабская область), которая в целом сохранялась вплоть до распада СССР.

Одесский округ изначально приобрёл стратегическое значение. С одной стороны он находился в непосредственной близости от Османской и Австро-венгерской империй, а с другой – включал в свои пределы берег Черного моря от устья Дуная до Керченского пролива. Таким образом, он вполне мог стать как ближайшей базой русских войск, действующих на Балканах (как это и случилось в 1877–1878 годах), так и театром военных действий в случае внешнего вторжения. В сферу его ответственности входили несколько важных портовых городов, речных артерий, крепостей.

Перед Коцебу стояла не простая задача сформировать целостную военно-административную единицу из ранее автономных соединений полевой армии, резервных батальонов, внутренней стражи, крепостной артиллерии, местных инженерных частей. Основой для создания округа стали дивизии упразднённого 5-го армейского корпуса и часть войск Сводного кавалерийского корпуса. Последний был расквартирован не только в Новороссии, но и в Курской, Харьковской и других губерниях. Его возглавлял принципиальный противник военно-окружной реформы генерал от кавалерии Иван Оффенберг. В итоге корпус был расформирован, а его бывший командир получил назначение в Военный совет Военного министерства.

К 1864 году Коцебу, как и главные начальники других округов сосредоточил в своих руках контроль над всеми войсками вверенного края: регулярными и иррегулярными, полевыми и местными, а также всеми военными учреждениями: артиллерийскими, инженерными, интендантскими, врачебными и другими. Группировка войск в рамках округа за два года возросла почти вдвое и составила пять дивизий (13–15-я, 34-я пехотные и 4-я кавалерийская). Больше войск концентрировалось только в Польше, Литве, на Кавказе и столичных округах.

Под руководством первого командующего округом шло становление местных войск, включавших резервные и губернские батальоны, уездные команды, крепостные гарнизоны, этапные команды, госпитальные и военно-арестантские роты.

6 августа 1864 года вступило в силу «Положение о военно-окружных управлениях». По отношению к личному составу войск и учреждений командующий округом наделялся властью командира отдельного корпуса в мирное время. По хозяйственной части он действовал как председатель Военно-окружного совета.

В практическом плане на начальника военного округа возлагались широкие административные функции по расквартированию, передвижению и снабжению войск, поддержанию дисциплины и охране здоровья военнослужащих, по военному обучению, инспектированию воинских частей и учреждений, аттестации военных кадров и их выдвижению на вышестоящие должности, рекрутским наборам, решению судебных дел и т. п.

В условиях войны армейские соединения, убывавшие на фронт переподчинялись главнокомандующим действующих армий. Округа, же затронутые военными действиями, также переходили под командование соответствующего главнокомандующего. Так, собственно, и произошло с Одесским военным округом во время войны 1877–1878 годов, когда он находился в подчинении Дунайской армии, обеспечивал прикрытие Северного Причерноморья от вражеских десантов, нёс основную нагрузку по интендантскому обеспечению войск на театре военных действий. Однако эти события происходили уже после того, как в начале 1874 года Коцебу был переведён из Одессы на пост начальника войск Варшавского военного округа.

Находясь на посту командующего в Причерноморье, Коцебу много сделал для удобного расположения войск, улучшения их материального положения, уровня обучения. Были построены новые казармы, военный госпиталь, открыты два юнкерских училища: пехотное в Одессе и кавалерийское в Елисаветграде.

Во время его генерал-губернаторства в Новороссии были осуществлены важные инфраструктурные проекты двойного (военно-гражданского) назначения. Железные дороги соединили Одессу, Николаев и Кишинёв с центральными губерниями империи, был углублён фарватер Керченского пролива, очищались Днепровские пороги, модернизировалось портовое хозяйство.

Совместно с формирующимся одесским самоуправлением царский наместник способствовал социально-культурному развитию административного центра генерал-губернаторства. Была проведена реформа судебных учреждений. В 1866 году центральные улицы были оснащены газовыми фонарями и замощены гранитом, в 1873 году проведён водопровод. В 1865 году на базе Решильевского лицея открылся Одесский университет, в котором пятью годами позже была учреждена стипендия имени П. Е. Коцебу.

Авторитет бывшего генерал-губернатора в Одессе был столь велик, что его имя продолжали увековечивать и после отъезда из города.

В память о Коцебу городская глазная больница долгое время именовалась Павловской. В настоящее время это Институт глазных болезней и тканевой терапии им. В. П. Филатова. В 1892 году в честь бывшего генерал-губернатора был назван вновь построенный мост по Полицейской улице (ныне – улица Бунина). На нём сохранилось изображение герба Одессы имперской эпохи (c двуглавым орлом и якорем). В 1914 году бюст Коцебу был установлен в здании Городской Думы.

Управление Новороссийским генерал-губернаторством и Одесским округом было высоко оценено имперским руководством.

Об этом свидетельствует пожалование ему в 1874 году графского титула, а также продолжение службы (в 1874–1880 годах) на аналогичных должностях в Польше. Варшавское генерал-губернаторство и военный округ имели в системе военно-государственной администрации Российской империи первостепенное значение.

В последние годы жизни графу Коцебу довелось сыграть важную роль в проведении военной политики всего Российского государства.

В октябре 1881 года под руководством бывшего шефа Одесского и Варшавского округов начала работать специальная комиссия для обсуждения вопросов о лучшем военном устройстве. В её состав входили главы ключевых военных округов, армейских корпусов, военных учебных учреждений. Присутствующими в комиссии состояли великие князья Николай Николаевич (старший), Михаил Николаевич и Владимир Александрович.

От имени комиссии Коцебу ходатайствовал перед императором о сохранении и укрупнении военных округов, расширении прав военно-окружных управлений и самостоятельности корпусных управлений.

Практическими следствиями этих предложений стало упразднение Харьковского военного округа в 1888 году (был разделён между Киевским и Московскими округами), создание мобилизационных и госпитальных отделений в составе окружных штабов, расширение интендантских управлений приграничных округов.

Скончался генерал от инфантерии, граф Коцебу в 1884 году в Ревеле. Ненадолго пережил его товарно-пассажирский пароход, названный его именем и спущенный на воду в 1866 году в Англии. В 1869 году двухпалубный колесный пароход