К I в. до н. э. на смену пришедшей в упадок Греции явилась ставшая величайшим в мире государством Римская империя. Распространив свои владения далеко на восток, она в столкновении с Понтийским царством разбила войска Митридата. Владения Митридата, в том числе Боспор и Херсонес, попали в подчинение Риму. С этого времени начинается постепенный упадок древних крымских городов, так как у Рима были более удобные, ближе расположенные районы, снабжавшие его хлебом, - Сицилия, Египет, Малая Азия и др. Пришла в упадок и Феодосия, занимавшая выдающееся место в экономической жизни края на протяжении нескольких веков. В древних письменных источниках начала II в. н. э. Феодосию называют "городом безлюдным", "городом опустевшим, имеющим гавань". Вероятно, это относится ко времени опустошительного набега каких-то кочевых орд в начале II в., после которого город временно опустел и пришел в упадок.
В более поздних источниках есть упоминание и о том, что "ныне Феодосия на алланском или таврском наречии называется Ардабда", что указывает на какой-то период, когда усилилась роль местного населения в исторических судьбах города. Несмотря на все это, Феодосия еще длительное время сохраняла свое значение в жизни Боспора. В государственном штате Боспора вплоть до IV в. существовала должность наместника Феодосии. Это свидетельствует о том, что и в римское время город продолжал обтаваться важным стратегическим и торговым пунктом. Об исторической роли Феодосии периода греческой колонизации в Крыму можно судить главным образом на основании письменных свидетельств античных писателей. Археологическими памятниками этой древней поры город почти не располагает. Такие материалы в огромном количестве найдены в соседнем с Феодосией Пантикапее и особенно в Херсонесе. Остатки памятников материальной культуры, найденные там археологами, помогают исторической науке нарисовать правдивую картину прошлой жизни народов, выяснить характер их общественно-экономических отношений и политического устройства.
В Херсонесе археологическими раскопками вскрыты остатки городских оборонительных стен и башен, фундаменты городских построек, среди которых найдено большое количество предметов быта, остатки ремесленных мастерских, предметы, относящиеся к сельскому хозяйству. Феодосия не знает находок подобного рода. Прежде объясняли это тем, что якобы нынешний город территориально не связан с древней Феодосией. Последнюю первоначально искали в различных местах: и у горы Опук, заметной в виде туманной возвышенности на восточном берегу Феодосийского залива, и в заливе у Отузской долины, в 30 километрах от города, а некоторые историки считали, что древняя Феодосия лежала неподалеку от современной, на южных склонах мыса св. Ильи. И. К. Айвазовский своими археологическими работами первый дал правильное определение местоположения античной Феодосии. Позднее, во время постройки Феодосийского порта в 1892-1894 гг., которой руководил инженер и крупный археолог А. Л. Бертье-Делагард, при земляных работах было найдено большое количество предметов, относящихся ко времени существования античной Феодосии. На дне моря, в черте нынешнего порта, были обнаружены остатки древнего свайного волнореза, существование которого также относится к античной эпохе. Там же были найдены в большом количестве остродонные кувшины (амфоры), в которых из Греции в Крым привозились вино и масло. Эти находки являются неопровержимым свидетельством того, что остатки древней Феодосии лежат под современным городом. Это же положение подкрепляется случайными находками черепков античных ваз у городского бульвара, на ул. III Интернационала, и наличием кургана, раскопанного Айвазовским.
На месте древней Феодосии на протяжении свыше двух с половиной тысяч лет жизнь никогда не замирала, город неоднократно разрушался до основания и вновь возникал из развалин. Поэтому естественно, что от древней Феодосии на поверхности земли ничего не оставалось. Археологическими раскопками, которые в течение последних лет проводил в Феодосии, на Карантинном холме, Московский музей изобразительных искусств имени А. С. Пушкина, на большой глубине вскрыт культурный слой, давший остатки строительных сооружений и предметы, относящиеся ко времени существования древнегреческой Феодосии. Нет сомнения, что расширение археологических раскопок даст новый научный материал, который поможет воссоздать древний облик многовекового города.
В IV в. в Скифию с востока вторглись полчища гуннов, опустошавших все на своем пути. Древние крымские города были в значительной степени разрушены. Под ударами гуннов пало и скифское государство. Местное скифское население было оттеснено в горные районы Крыма, где оно смешалось с таврами и стало именоваться тавро-скифами. Из всех древних городов Крыма уцелел только Херсонес. К этому времени Римская империя распалась на Восточную и Западную. К восточной части — к Византии — отошли страны восточной половины Средиземного моря и многие бывшие греческие и римские колонии на Черном море. Столицей Византийской империи являлся город Константинополь. Византия в течение нескольких веков была крупнейшим государством мира.
Крым в экономике Византии занимал значительное место. В борьбе с кочевыми народами, наводнявшими крымские степи, Византия опиралась на свой главный город в Крыму — Херсонес. Гунны не задержались в Крыму. Начиная с IV в., через южнорусские степи в Крым, помимо гуннов, прошли различные кочевые народы: авары, печенеги, болгары, хазары, половцы и др. С VI в. в горной части Крыма начинают формироваться новые государственные образования - средневековые княжества, в которых складывается феодальный общественный строй. В истории старых крымских городов наступает длительный "глухой" период. О жизни этих городов в эпоху раннего средневековья сохранились очень скудные отрывочные сведения.
Археологический материал, обнаруженный на территории древних городов, также беден. Отдельные археологические находки, относящиеся к IX-X вв., дают основание утверждать, что и в эту эпоху на месте Феодосии было поселение и, видимо, достаточно экономически мощное, если судить по большим мраморным капителям, найденным в городе, но уже перетесанным в более позднюю пору на чаши для воды. Отдельные капители этой поры до Великой Отечественной войны поддерживали аркады вдоль домов по главной улице Феодосии.
В ближайшем соседстве с Феодосией, в п.Коктебель, археологическими раскопками обнаружено большое поселение. Оно возникло в VII-VIII вв. и просуществовало до половины X в. Находки на этом городище свидетельствуют о наличии славянского населения среди его жителей и о культурных связях поселения с Киевской Русью и складывавшимся Тмутараканским княжеством на Таманском и Керченском полуостровах. Появление славян в Крыму относится к глубокой старине.