Однако с римской крепостью, так же как и с греческой Диоскурией, по-видимому, произошло какое-то стихийное бедствие, которое надолго привело этот край в запустение. Вплоть до VI в. никаких сведений о Себастополисе не поступало. Лишь в середине VI в. византийский историк Прокопий Кесарийский упоминал о небольшой «крепостице», лежащей на пути от Лазики к Азовскому морю. В это время император Юстиниан I вел борьбу с персами за обладание Черноморским побережьем Кавказа. Не рассчитывая на прочность стен своих крепостей Питиуса (Пицунды) и Себастополиса, он в 550 г. разрушил их и отвел из них гарнизоны. Однако вскоре византийцам удалось вернуть потерянное, и они вновь восстановили крепость Себастополис, построив его там же, но на более высоком месте. Теперь уже тот же Прокопий Кёсарийский в своей «Истории войн» написал: «Император Юстиниан сей самый Себастополис, который прежде был не более как крепость, возобновил и стенами, и другими способами, так что город этот по обширности и богатству стал одним из первых на восточном побережье Черного моря».
Но после этого сведения о древнем городе окончательно исчезают. Лишь в XVII в. итальянский миссионер Арканжело Ламберти в своих записках отмечает, что «пятое аббатство было Севастопольское, которое теперь поглощено водой». Однако местонахождение этого Севаста, или Сан-Себастьяна, как называли его еще генуэзские письменные источники, никому неизвестно. За долгое время турецкого владычества память об античных городах стирается настолько, что после присоединения Крыма к России, как уже сообщалось выше, за Себастополис были ошибочно приняты руины Херсонеса.
Путаница продолжалась и в наше время, хотя большинство ученых не сомневались, что Диоскурию и Себастополис надо искать на Кавказе. Однако одни полагали, что это разные города, другие считали, что Диоскурия лежала в устье р. Риони, которая у древних греков называлась Фазисом, ведь именно сюда устремлялись аргонавты за золотым руном. Некоторые исследователи обращали внимание на устье р. Кодоры, где отдельные урочища имели созвучные названия: Искурия, Скурча.
Конечно, неоднократно историки исследовали и расположенную на самом берегу моря и подмытую волнами Сухумскую крепость. Одна часть исследователей предполагала, что это — участок знаменитой «Великой Абхазской стены». Однако известно, что первое ее звено находится в 5 км южнее Сухуми, возле впадения в море р. Келасури. Другие, менее оптимистично настроенные историки утверждали, что у моря стоит не представляющая большой ценности крепость XVII–XVIII вв. Однако под ее «турецкими» стенами некоторые ученые предполагали найти более раннюю античную кладку. Но когда в 1926 г. произошел обвал крепостных стен, профессор А.С. Башкиров после осмотра обнажившегося каменного основания установил, что оно относится к XI–XIII вв., т.е. к эпохе объединенного Грузинского государства. Таким образом, казалось, вопрос был решен окончательно. К тому же позднее, в 1952–1953 гг., постройка сухумской набережной окончательно похоронила под асфальтом мостовой остатки древних стен, и возрастом Сухумской крепости совсем перестали заниматься.
