Проезжая по Новороссии, Бенкендорф отдал должное гению Потёмкина, по его словам, «творца всего Юга России».
В Херсоне, тогда ещё гордившемся званием главной базы Черноморского флота, Бенкендорф не мог не признать величия сделанного всего двумя десятилетиями ранее: «Значительный город, внушительная крепость, активная торговля, которую ведёт Херсон, — всё это тоже деяние Потёмкина, этого — можно даже наградить его титулом высшего должностного лица побеждённой им империи — визиря императрицы, великого и замыслами, и талантами, и пороками». С заметными нотками сожаления записывает Бенкендорф историю о том, как в царствование Павла был разорён мавзолей «визиря», а его тело выброшено в волны Днепра. Сделанный из неё вывод перекликается с его личным опытом: «Низость придворных всегда идёт дальше желаний тиранов»…
В Херсоне Бенкендорфа и других своих подчинённых дожидался «старина генерал». В его планах были не только Новороссия и Крым, но и Константинополь, и Греческий архипелаг, с посещением которого экспедиция должна была завершиться.
Бенкендорф начинает задумываться о будущем. 5 марта 1804 года он пишет Воронцову письмо, где делится полупланами, полусомнениями: «Я ещё не знаю, чего и желать. Хочется объехать архипелаг, повеселиться в Италии, видеть Берлин и через Польшу возвратиться домой, но в таком случае, если войны не будет; а коли скоро наши войска тронутся, то ни за что не останусь при генерале или в чужих краях. Если князь Павел Дмитриевич (Цицианов. — Д. О.) останется главнокомандующим в Грузии, то с радостию и под Эривань постараюсь поспеть… Ты видишь, любезный Михаил Семёнович, не ведаю, что со мной будет, и жду на это от Ливена письма»>16. (Зять Бенкендорфа генерал X. А. Ливен всё ещё оставался начальником Военно-походной канцелярии Его Императорского Величества, и от него во многом зависели будущие назначения.)
В начале весны, когда в сборе были все участники экспедиции, Спренгтпортен направился в Крым, завоевание которого было ещё совсем недавней историей. Бенкендорф снова вспоминает Потёмкина; но, наблюдая пустынные земли от Перекопа до Ак-Мечети (Симферополя), то есть на протяжении более 100 вёрст, он составляет весьма критическое мнение о присоединении полуострова: «Справедливости ради следует сказать, что вечным позором для завоевателей и для царствования Екатерины будет то, что эта прекрасная область, когда-то житница Константинополя и всей Малой Азии, покрытая городами с цветущими садами и питавшая более миллиона трудолюбивых жителей, была превращена в пустыню. Весь Крым сделался безлюдным». Добравшись до Кафы (Феодосии), Бенкендорф расстроился ещё больше: «Весьма просторная бухта была некогда заполнена судами; теперь здесь нет и полутора сотен жалких лачуг, ни тени торговли; разруха и нищета овладели этим городом с того момента, как он перешёл под власть великой Екатерины. Находясь в Кафе, испытываешь стыд; татары здесь искусно строили, русские всё варварски разрушили». Удручённое настроение усугубляет поразившая молодого поручика красота Крымского побережья, тогда практически неизвестная в России. Он отправляется на прогулку пешком от Феодосии до Судака, пересекает знаменитые «плюшевые» холмы в районе Коктебеля, взбирается на гору с генуэзской крепостью и с её высоты любуется «незабываемым видом на безбрежные дали Чёрного моря». По воспоминаниям видно, как романтические и поэтические чувства захлестывали 22-летнего офицера: «Весь этот край завораживает древностью и легендарностью своей истории, потрясениями, которые он испытал, народами, которые его населяли и, сменяя друг друга, владели этой землёй, — следами присутствия греков, генуэзцев, татар и вот теперь — русских».
