Павел Евстафьевич Коцебу, ставший последним генерал-губернатором Новороссии и первым командующим Одесским военным округом родился 10 августа 1810 года. Делом его жизни была военная служба, он прошёл Кавказскую и Крымскую войны. Высоких постов при дворе и правительстве до конца жизни Коцебу не занимал, и это стало исключением из правил
Со времён Григория Потёмкина и Армана-Эммануэля де Ришелье наместники Причерноморья назначались из числа вельмож или именитых иностранцев. Причины этого новшества крылись в реформаторских проектах Александра II.
С начала своего правления император-реформатор взял курс на упразднение генерал-губернаторств как промежуточного звена в управлении между имперскими и губернскими учреждениями. Вероятно, Новороссийское генерал-губернаторство перестало бы существовать ещё в 1850-60-е годы, если бы потрёпанное Крымской войной Причерноморье не нуждалось в особой опеке со стороны центральных властей.
Генерал-губернатор, граф Александр Строганов (приложивший руку к появлению знаменитого блюда "Бефстроганов") обеспечил тогда эффективный контроль над работой государственных учреждений в Новороссийских губерниях. С другой стороны, добившись введения городского самоуправления в столице наместничества Одессе он не в малой степени снизил значение своей собственной должности.
Коцебу был официально назначен на должность Новороссийского и Бессарабского генерал-губернатора в декабре 1862 года. Через 2 дня после этого события (25 декабря) был учреждён Одесский военный округ и Коцебу принял на себя командование им.
Военно-окружная система вводилась в рамках армейских реформ Дмитрия Милютина. Своей целью это преобразование имело улучшение управляемости войск и децентрализацию системы контроля над армейскими структурами. Создание первых четырёх округов (Виленского, Варшавского, Киевского и Одесского) произошло в августе-декабре 1862 года как своеобразный эксперимент на основе временного положения.
Три из четырёх первых командующих округами являлись одновременно главами соответствующих генерал-губернаторств (в Прибалтике, Малороссии и Новороссии). Будучи кадровым военным Коцебу рассматривался в Петербурге как компетентный и энергичный реализатор военно-окружной реформы, достойный военный руководитель на важнейшем Балканском направлении.
Это первоначальное совмещение гражданской и военно-административных должностей определило территорию ответственности Одесского военного округа (Херсонская, Таврическая, Екатеринославская губернии и Бессарабская область), которая в целом сохранялась вплоть до распада СССР.
Одесский округ изначально приобрёл стратегическое значение. Он находился в непосредственной близости от Османской и Австро-венгерской империй, а с другой — контролировал берег Чёрного моря от устья Дуная до Керченского пролива. Таким образом, он вполне мог стать как ближней базой русских войск, действующих на Балканах (как это и случилось в 1877-78 годах), так и театром военных действий в случае внешнего вторжения.
Перед Коцебу стояла задача сформировать целостную военно-административную единицу из ранее автономных соединений полевой армии, резервных батальонов, внутренней стражи, крепостной артиллерии, местных инженерных частей. Основой для создания округа стали дивизии упразднённого 5-го армейского корпуса и часть войск Сводного кавалерийского корпуса. Последний был расквартирован не только в Новороссии, но и в Курской, Харьковской и других губерниях. Его возглавлял принципиальный противник военно-окружной реформы генерал от кавалерии Иван Оффенберг. В итоге корпус был расформирован, а его бывший командир получил назначение в Военный совет Военного министерства.
К 1864 году Коцебу, как и главные начальники других округов сосредоточил в своих руках контроль над всеми войсками вверенного края: регулярными и иррегулярными, полевыми и местными, а также всеми военными учреждениями: артиллерийскими, инженерными, интендантскими, врачебными и другими. Группировка войск в рамках округа за два года возросла почти вдвое и составила пять дивизий. Больше войск концентрировалось только в Польше, Литве, на Кавказе и столичных округах.
Под руководством первого командующего округом шло становление местных войск, включавших резервные и губернские батальоны, уездные команды, крепостные гарнизоны, этапные команды, госпитальные и военно-арестантские роты.
6 августа 1864 года вступило в силу "Положение о военно-окружных управлениях". По отношению к личному составу войск и учреждений командующий округом наделялся властью командира отдельного корпуса в мирное время. По хозяйственной части он действовал как председатель Военно-окружного совета.
В условиях войны армейские соединения, убывавшие на фронт переподчинялись главнокомандующим действующих армий. Округа, же затронутые военными действиями, также переходили под командование соответствующего главнокомандующего. Так, собственно, и произошло с Одесским военным округом во время войны 1877-78 годов, когда он находился в подчинении Дунайской армии, обеспечивал прикрытие Северного Причерноморья от вражеских десантов, нёс основную нагрузку по интендантскому обеспечению войск на театре военных действий. Однако эти события происходили уже после того, как в начале 1874 году Коцебу был переведён из Одессы на пост начальника войск Варшавского военного округа.
Находясь на посту командующего в Причерноморье, Коцебу много сделал для удобного расположения войск, улучшения их материального положения, уровня обучения. Были построены новые казармы, военный госпиталь, открыты два юнкерских училища: пехотное в Одессе и кавалерийское в Елисаветграде.
Железные дороги соединили Одессу, Николаев и Кишинёв с центральными губерниями империи, был углублён фарватер Керченского пролива, очищались Днепровские пороги, модернизировалось портовое хозяйство.
Совместно с одесским самоуправлением наместник способствовал социально-культурному развитию административного центра генерал-губернаторства. Была проведена реформа судебных учреждений. В 1866 году центральные улицы были оснащены газовыми фонарями и замощены гранитом, в 1873 году проведён водопровод. В 1865 году на базе Решильевского лицея открылся Одесский университет, в котором пятью годами позже была учреждена стипендия имени П.Е. Коцебу.
Авторитет бывшего генерал-губернатора в Одессе был столь велик, что его имя продолжали увековечивать и после отъезда из города.
В память о Коцебу городская глазная больница долгое время именовалась Павловской. В настоящее время это Институт глазных болезней и тканевой терапии им. В.П. Филатова. В 1892 году в честь бывшего генерал-губернатора был назван вновь построенный мост по Полицейской улице (ныне — улица Бунина). На нём и сегодня сохранилось изображение герба Одессы имперской эпохи (c двуглавым орлом и якорем). В 1914 году бюст Коцебу был установлен в здании Городской Думы.
Управление Новороссийским генерал-губернаторством и Одесским округом было высоко оценено имперским руководством.
Об этом свидетельствует пожалование ему в 1874 году графского титула, а также продолжение службы (в 1874-80 годах) на аналогичных должностях в Польше. Варшавское генерал-губернаторство и военный округ имели в системе военно-государственной администрации Российской империи первостепенное значение.
В последние годы жизни графу Коцебу довелось сыграть важную роль в проведении военной политики всего Российского государства.
В октябре 1881 году под руководством бывшего шефа Одесского и Варшавского округов начала работать специальная комиссия для обсуждения вопросов о лучшем военном устройстве. В её состав входили главы ключевых военных округов, армейских корпусов, военных учебных учреждений. Присутствующими в комиссии состояли великие князья Николай Николаевич (старший), Михаил Николаевич и Владимир Александрович.
От имени комиссии Коцебу ходатайствовал перед императором о сохранении и укрупнении военных округов, расширении прав военно-окружных управлений и самостоятельности корпусных управлений.
Практическими следствиями этих предложений стало упразднение Харьковского военного округа в 1888 года (был разделён между Киевским и Московскими округами), создание мобилизационных и госпитальных отделений в составе окружных штабов, расширение интендантских управлений приграничных округов.
Скончался генерал от инфантерии, граф Коцебу в 1884 году в Ревеле. Ненадолго пережил его товарно-пассажирский пароход, названный его именем и спущенный на воду в 1866 году в Англии. В 1869 году двухпалубный колёсный пароход "Генерал Коцебу", имевший российскую делегацию на борту, стал первым пароходом, вошедшим в Суэцкий канал. В апреле 1895 года после столкновения с другим пароходом у берегов Крыма он затонул.
В 2013 г. дайверы Черноморского центра подводных центра смогли попасть на пароход, лежащей на глубине 44 метров западнее полуострова Тарханкут. С него была подняты несколько предметов, которые находятся в Феодосийском филиале центра.
А в 2018 году российской экспедицией "Нептун" в одном из нижних трюмов были обнаружены картины, которые могли быть написаны Иваном Айвазовским.
Одесский военный округ пережил гибель Российской империи и продолжил существовать в Советском Союзе. Как известно, в послевоенные годы его войсками командовал сам Георгий Константинович Жуков.
В 1998 году на базе Одесского военного округа было создано Южное оперативное командование. В 2006 году наследник основанного Коцебу Одесского военного училища — Институт сухопутных войск, был фактически ликвидирован и переведён во Львов. В 2013 году штаб Южного оперативного командования был переведен из Одессы в Днепропетровск.
Только события 2014 года и последовавшая за ним милитаризация Украины вынудили руководство страны поднять военно-административное значение Одессы. Правда это цели, которые при этом поставлены перед расквартированными в Одессе военными Павла Евстафьевича Коцебу сильно бы удивили, и еще больше бы расстроили.