Тракт в Севастополь был уже накатанный, освоенный. В России его обсаживали сосной, елью, берёзой и липой. По мере того как он спускался к югу, менялись и посадки — дальше шли дубы, пирамидальные тополя, яблони, груши, а в Крыму больше было карагача и акаций. Перед поездкой Фаддей прочитал о Севастополе всё, что хранилось в Кронштадтской библиотеке, расспрашивал тех, кто уже бывал там. Мнения разнились. Одни вспоминали пыль и жару, другие восторгались тамошним климатом, дешевизной овощей и фруктов, добротой и детской хитростью жителей. Но сходились в одном — это был истинно служивый город, открытый и устроенный русскими моряками, ими же ухоженный и приспособленный для более или менее сносной жизни. Начался Севастополь задолго до того, как Фаддей впервые смахнул с губы морскую соль.
Князь Потёмкин-Таврический послал вице-адмирал Клокачева подыскать на Крымском побережье удобную стоянку для всё разрастающегося флота. К поручению Клокачев отнёсся серьёзно, вскоре нашёл-таки то, чего искал светлейший. Он наткнулся на так называемую Ахтиарскую бухту, сюда когда-то заходили древние греки, а позже при татарах её забросили.
«При самом входе в Ахтиарскую гавань дивился я её хорошему расположению, — писал Клокачев, — а вошедши и осмотревши, могу сказать, что по всей Европе нет подобной сей гавани положением, величиной и глубиной; можно иметь в ней флот до ста кораблей. Ко всему тому природа устроила такие лиманы, что сами по себе отделены на разные гавани. Без собственного обозрения нельзя поверить, чтобы так сия гавань была хороша. Ныне я принялся аккуратно гавань и положение её мест описывать и, коль скоро кончу, немедленно пришлю карту. Ежели благоугодно будет её императорскому величеству иметь в здешней гавани флот, то на подобном основании надобно будет завести, как в Кронштадте».
Клокачев к делу подключил подштурмана Ивана Батурина. Тот выполнил съёмку местности, составил подробную карту, указал в описи глубины вахты, господствующие ветры, грунты побережья и всё то, что полагается в таких случаях. В 1773 году карта легла на стол светлейшему князю. Хоть в то время Таврический занимался войной с турками, одноглаз был ленив порою, но бухту решил осмотреть самолично. А увидев её, обойдя и объездив, велел город строить — и как можно поспешней.
Вблизи была татарская деревенька. Она укрыла на зиму первых русских поселенцев — 2600 душ с кораблей. Из ноздреватого инкерманского камня матросы стали возводить казённые дома, пристани, устраивать дороги, водопровод, адмиралтейский штаб, парадный причал. Потёмкин этот причал приказал именовать Екатерининским в честь матушки-государыни, но закрепилось за ним название Графский, поскольку шлюпка местного начальника графа Войновича причаливала и отваливала именно в этом месте.
Следом за моряками наехали лавочники, трактирщики, стряпухи и другие обыватели, обслуживающие флотских. Севастополь воевал и строился. Появились хутора, сады, общественный сад в Ушаковской балке, Артиллерийская и Корабельная слободки, плотно застроенная Городская сторона.
Укрепления Севастополя походили на кронштадтские, а там использовались идеи Марка Рене Монталамбера — генерал-инженера, автора системы фортификации в Шербуре, где грозную силу представляли крепостные бастионы с двумя-тремя ярусами орудий. Причём орудия нижних ярусов устанавливались в казематах — небольших сводчатых помещениях, укрытых от вражеского огня.
Фаддей по дороге ожидал попасть в заштатную дыру, но приятно удивился, увидев опрятный и красивый город у ярко-голубого, в солнечной чешуе моря. Ещё более поразился он отношению севастопольцев к бывшему командующему флотом, нынешнему морскому министру Жану Франсуа де Траверсе. Били его каменьями и современники, и историки. И, мол, расшаркивающийся царедворец, и прескверный мореход... Но во всём ли надо было винить честного провансальца? Как понял Фаддей, служа на флоте Балтийском, находившемся ближе всех к столице, Александр I Благословенный к морскому ведомству добрых чувств не питал. А назначенный командовать Черноморским флотом в 1802 году Траверсе поначалу много потрудился над укреплением его главной базы. Он понимал, что её надо укрепить не только со стороны моря, но и с суши. Перво-наперво он предложил государю весь город обнести сплошными каменными стенами, благо такого материала было вдоволь, с надлежащими фортификационными сооружениями. Потом представил ещё несколько проектов, касавшихся Севастополя и его роли в противоборстве с турками и другими неприятелями. Однако царь, занятый войной с Францией, проекты забраковал, наложив резолюцию: «Хранить до востребования». Так французский маркиз Жан Франсуа, русский Иван Иванович, почёл за благо не докучать императору разными прожектами и пустил флот по воле волн...