Осенью того года Сенявин был переведён на только что построенный фрегат «Крым», а в январе 1783 года произведён в чин лейтенанта.
Образцового, расторопного офицера присмотрел младший флагман, контр-адмирал Мекензи, и Сенявин 2 мая 1783 года с эскадрой вице-адмирала Федота Клокачева вошёл в Ахтиарскую бухту. Флагман Клокачев сразу оценил Ахтиарскую гавань по достоинству. «О которой могу вам объявить, — сообщал он в письме, — подобной ещё гавани не видали, в Европе действительно таковой хорошей нет; вход в сию гавань самый лучший, натура сама разделила бухту на равные гавани, т. е. военную и купеческую, довольная в каждом лимане глубина, положение ж берегового места хорошее и надёжно к здоровью, словом сказать, лучше нельзя найти к содержанию флота места».
Вскоре Клокачев убыл в Херсон, а новый флагман Мекензи поручил своему адъютанту обустраивать гавань и порт. Томас Мекензи больше занимался личными делами, «спроворил себе дачу», балагур по натуре, он любил повеселиться. «Ко всему этому, адмирал наш, — заметил Сенявин, — очень любил давать празднества и беспрестанно веселиться, что была так же страсть его. В каждое воскресенье и торжественные дни у него обед, а ввечеру бал. Ни свадьба, ни крестины и даже похороны без присутствия его не обходились, везде он бывал, а потом все у него обедают и танцуют всегда почти до рассвета».
Все заботы по строительству порта и города Мекензи постепенно переложил на Сенявина.
Неделями без отдыха метался флаг-офицер по бухточкам и берегам. Договорился с командирами полков — на стройки стали высылать солдат в помощь матросам. Съездил в Балаклаву, подрядил тамошних мастеровых-каменщиков. Не хватало материалов — Сенявин приказал брать камень в Херсонесской бухте. Доставляли на тех же самых карбасах, которые здесь отыскали полгода назад. Мекензи обычно отмахивался от просьб своего флаг-офицера — доложить начальству о нехватке леса, камня, и тогда Сенявин сам обратился в Адмиралтейство.
Постепенно всё наладилось, и весной 1784 года Севастополь уже обозначился первой улицей с каменными домами. Слева от пристани расположились кузницы, склады, шлюпочный эллинг. Инженеры и артиллеристы полков к этому времени укрепили на мысах при входе в Ахтиарскую бухту батареи, сооружённые Суворовым для отражения возможного нападения с моря.
«Построили первую часовню „Святого Николая“, — так отметил Сенявин в своих записках это знаменательное событие. — Часовня освящена 6 августа, кузница была готова в три недели, пристань сделана с небольшим в месяц, а в дом перешёл адмирал и дал бал на новоселье 1 ноября. Вот откуда начало города Севастополя».
Осенью корабли эскадры салютовали первенцу херсонских верфей, 70-пушечному кораблю «Слава Екатерины» под командой капитана 1-го ранга Марка Войновича.
Минул год. У самого входа в Южную бухту неподалёку от приметного мыска загрохотал якорь, отданный 50-пушечным фрегатом «Святой Павел». Фрегат встал на якорь лихо, без суеты и излишнего шума. Капитан 1-го ранга Фёдор Ушаков отдал команду:
— Опустить шлюпки. Экипажу дозволено на дна часа съехать на берег.
К прибывшим кораблям Мекензи относился с прохладцей. Больше занимался увеселениями и своими делами. Осенью, когда в Севастополе объявилась ревизия, посланная Потёмкиным, который с того года стал главнокомандующим нового Черноморского флота, Мекензи сразу сказался больным и устранился от проверки. Ревизия обнаружила крупные недостачи, и высочайшим повелением «главный командир» был привлечён к ответственности «за неправильное расходование казённых сумм». После этих событий Мекензи занемог по-настоящему, проболел недолго и после Рождества скончался.
Вместо него Потёмкин назначил своего протеже Войновича. Вступив в должность, Войнович хотел оставить при себе Сенявина флаг-офицером. Сенявин согласился, но попросил:
— Ваше превосходительство, должность сия отлучила меня от службы корабельной. Посему, оставаясь при вас, желал бы предстоящую кампанию самостоятельно судном управлять.
Потёмкин сам указал на Сенявина:
— Нынче с Константинополем сношения обретают важный смысл. Посланник наш, Булгаков, просил надёжного офицера отыскать.
Русский посланник Яков Иванович Булгаков обрадовался новому человеку из России. За двадцать лет дипломатической службы он научился с одного взгляда оценивать людей. Сенявин пришёлся ему явно по душе. За обедом он рассказывал новому знакомому о разных интригах и происках дипломатов в Стамбуле. Частенько они не ладили, но потом сходились и мирились, чтобы сообща воздействовать на Порту.