После присоединения Крымского полуострова к Российской империи началась новая эпоха в истории города. Уже в начале следующего, 1784 г. Кефу (Каффу, Кефе) переименовали в Феодосию. На волне так называемого греческого проекта (в российских верхах в то время витали идеи создания греческого государства во главе с внуком Екатерины II Константином) и в память о древних эллинских поселениях Причерноморья многие из городов в новых русских владениях получили греческие названия. Но только Кефе (отчасти случайно) вернули ее подлинное древнее имя. Впервые город был назван Феодосией в правительственном Указе от 10 (21).02.1784 г.: "Город Феодосию (Кефу)... укрепить, поправя старые замки и снабдя их артиллериею". Однако неофициально Феодосию, еще долго находившуюся как бы в тени своей предшественницы, часто называли Каффой (Кефой). На некоторых европейских географических картах название "Каффа" вместо "Феодосия" встречалось вплоть до середины XIX в. и даже позже.
Несколько раз в конце XVIII - начале XIX в. менялся административный статус города. До 1787 г. Феодосия находилась в составе Левкопольского уезда Таврической области. В 1787-1796 гг. она становится уездным центром в Таврической области. После упразднения последней входит в состав Симферопольского уезда Новороссийской губернии. В октябре 1802 г. превращается в уездный город Таврической губернии.
Переселение христиан в Приазовье в 1779 г. и массовая эмиграция мусульман после Указа о присоединении Крыма к России резко сократили численность населения полуострова, особенно приморских городов. В подробном описании к плану Феодосии 1784 г. названо 20 греческих домов, 30 армянских, 697 турецких, 69 еврейских; 29 мечетей, 13 греческих церквей, 22 армянские церкви, 6 общественных бань, 33 фонтана и водоема, загородный ханский дворец с монетным двором, несколько караван-сараев. Из 813 находившихся в городе домов большинство пустовало.
В конце XVIII в. Кефа-Феодосия утратила свое ведущее положение в торговле Северного Причерноморья. Округа города была малолюдна и разорена, отсутствовали удобные дороги между феодосийской гаванью и внутренними районами страны. В результате обладавший великолепной гаванью город не мог на равных конкурировать с новыми российскими портами на Черном море, расположенными ближе к сырьевым районам страны или находившимися на берегу судоходных рек. Резкое уменьшение численности населения (в 1787 г. в городе проживало около 2000 человек, в 1800 г. - 50 семей, в 1802 г. - 290-323 человека) и упадок торговли привели его в конце XVIII в. к глубочайшему кризису.
Правительство делает попытки возродить былое торговое значение Феодосии. Вскоре после присоединения Крыма к России здесь устраивается одна из трех главных таможен Крыма. В 1787-1788 гг. на бывшем ханском монетном дворе чеканится русская "Таврическая" монета. В 1787-1799 гг. Феодосия становится центром православной Феодосийско-Мариупольской викарной епархии. Епископы Феодосийско-Мариупольские служили в старинной феодосийской греческой Введенской церкви. Городу и его жителям (особенно новым поселенцам) предоставлялись торговые и другие льготы. Но возрождению помешала новая война с турками, и жизнь в городе постепенно замирала. С упразднением в 1796 г. Таврической области он вообще был исключен из списка штатных городов империи.
Еще одна попытка возродить Феодосию предпринимается в 1798 г. в связи с учреждением в Крыму порто-франко, то есть беспошлинной торговли. Феодосийская и евпаторийская гавани определяются для ввоза на полуостров заграничных товаров и вывоза за рубеж отечественных. Кроме того, Феодосия, которой возвращается статус города, назначается "главным пристанищем для приезжающих в Крым греков", получивших здесь значительные льготы и привилегии. Но режим беспошлинной торговли не привел к экономическому расцвету края. В конце 1799 г. порто-франко упразднили, и с его отменой, казалось, растаяли все надежды на возрождение города.
Новые российские владения на берегах Черного моря, особенно Крым с его восточным колоритом, разноязыким населением и многочисленными памятниками истории, природы привлекали к себе как просвещенных соотечественников, так и иностранцев. Феодосия (а точнее - руины Каффы) посещалась всеми путешествовавшими по полуострову в конце XVIII в., в том числе самой императрицей Екатериной II. ( В XIX - начале XX в. Феодосию посещали российские императоры Александр I, Николай I, Александр II, некоторые из Великих князей.) Она побывала здесь во время предпринятого ею в 1787 г. грандиозного по своим масштабам "путешествия в полуденные страны России".
"Мая 28. Всемилостивейшая Государыня и Граф Фалкенштейн изволили ездить в город Феодосию ... и после обеденного стола возвратились в Старый Крым в шестом часу пополудни. При въезде в Феодосию ... и во время отбытия оттуда была производима пушечная пальба. Ея Величество с Графом Фалкенштейном (австрийский император Иосиф II.) благоволили осматривать Феодосийский Монетный двор (бывший ханский монетный двор, на котором в 1787-1788 гг. чеканилась русская монета) и все фабрики, к деланию монеты принадлежащие; тут в Высочайшем присутствии тиснуты две золотые медали и поднесены Генералом-Фельдмаршалом Князем Григорьем Александровичем Потемкиным Ея Императорскому Величеству и Графу Фалкенштейну, с означением года, месяца и дня, в который соизволили быть на Феодосийском Монетном дворе" (Журнал Высочайшего путешествия Ея Величества Государыни Императрицы Екатерины II, самодержицы Всероссийской, в полуденные страны России в 1787 г.).
В эти же годы были составлены первые серьезные научные описания Крыма. Многие научные труды, а также дневники и путевые заметки чиновников и дипломатов, шпионов, ученых и праздных вояжеров позднее были изданы. Сегодня они являются важнейшим источником по истории полуострова, отдельных местностей, городов, в том числе Феодосии. Яркие описания Феодосии конца XVIII в. оставили французский ученый Жильбер Ромм (1786 г.), академик П.-С. Паллас (1793-1794 гг.), русский писатель П. Сумароков (1799, 1802 гг.).
Ж. Ромм: "В этом городе, заслужившем благодаря своей населенности название Малого Константинополя, в настоящее время насчитывается 488 татар, в том числе 276 женщин, около 700 армян, немного греков и евреев. Торговля его была значительной; теперь здесь торгуют только солью... Продают в шитых мехах...сыромятные бычьи кожи... телячьи кожи... кожи овечьи и козьи. Турки привозят из Анатолии фрукты, ткани и медь, которая идет на Феодосийский монетный двор. Русские покупают ее... продавая туркам соль... Монетный двор... расположен подле дворца, который хан строил себе на берегу моря и который так и остался незаконченным. Машины, прессы для чеканки и здание фабрики принадлежали хану. В городе прежде было несколько замечательных зданий, из которых и посейчас сохранились две большие мечети и нарядно разукрашенная мрамором баня... Мне говорили, что у феодосийских евреев есть ценные рукописи".
П.-С. Паллас: "От этого столь населенного и цветущего некогда города остались только большие массы развалин и груды камней, как бы затем, чтобы свидетельствовать о его древнем величии... с того времени, как русские сделались обладателями Крыма, война с турками и еще больше эмиграция до такой степени обезлюдили этот город, что теперь, за исключением нескольких небольших жилых кварталов, все остальное представляет громадные кучи мусора. Два предместья... ныне почти разрушены... За городом у бухты находились монетный двор, обращенный теперь в казармы, и дворец хана Шагин-Гирея, неоконченный постройкой".
П. Сумароков (1799): "Ныне в Кафе считается до ста небольших только и худо построенных домиков, и обитатели оного суть вновь пришлые уже греки, армяне и жиды, караимы, но ни одного татарина в нем не находится, ибо старожилы все удалились внутрь Крыма, другие же и совсем его оставили... Кафа пользуется преимуществом порто-франко... по причине пустоты сего края, скудости жителей, за неимением в Кафе контор, магазинов, притом малого привоза из России сюда товаров... торговля в Кафе, равно и по всему Крыму, не в цветущем пребывает состоянии".