В декабре 1837 года на должность градоначальника Одессы был назначен граф, генерал-майор Александр Петрович Толстой. Эту должность он занимал до февраля 1840 г., когда после конфликта с князем М.С. Воронцовым, вышел в отставку и уехал за границу. 

Александр Петрович родился 28 января 1801 года в Санкт-Петербурге, получил домашнее образование. Рано начал военную службу. В 1824-1826 гг. находился в походах с экспедицией по обозрению Каспийского и Азовского морей и истреблению морских разбойников, принимал участие во всех военных действиях отряда и был награжден орденом св. Владимира 4-й степени с бантом. По возвращении из экспедиции в 1826 году оставил военную службу и поступил в Коллегию иностранных дел. 

В 1828 году из-за войны с Турцией, снова поступил на военную службу в тот же Кавалергардский полк и принимал участие в походах и военных действиях под командованием генерала Дибича. В августе 1829 г. назначен флигель-адъютантом к Императору Николаю I, однако после окончания войны решил продолжать службу по Министерству иностранных дел и в феврале следующего года вышел в отставку. 

В 1830 получил придворное звание камергера и назначение первым секретарем Русской миссии в Греции. В 1831 Толстой служит сначала управляющим, а затем директором Хозяйственного департамента. В 1834 он уже действительный тайный советник, занимает пост Тверского гражданского губернатора. 

После того как Толстой покинул Одессу в течение 15-ти лет он стоял в стороне от государственной и общественной деятельности. К службе Толстой вернулся в мае 1855, во время крымской войны, когда принял должность начальника Нижегородского ополчения, и в дальнейшем занимал крупнейшие государственные посты - обер-прокурора Святого Синода (1856-1862 гг.), затем до конца жизни был членом Государственного совета. С декабря 1856 года - генерал-лейтенант. 

Толстой был другом Н. В. Гоголя, который умер в его доме. Гоголя привлекало в Толстом многое, в частности, - природная доброта, религиозная настроенность души, склонность к аскетизму. Он был одним из замечательнейших людей, встреченных на жизненном пути. Его личность производила неизгладимое впечатление на всех, кто, так или иначе, соприкасался с ним. 

Александр Петрович был женат на княгине Анне Георгиевне Грузинской (31.01.1798 – 17.07.1889, Москва), детей у них не было. 

Александр Петрович Толстой умер 21 июля 1873 года в Женеве.