Перші фортечні споруди побудували тут візантійці у 6-7 століттях. Потім фортецею заволоділи хазари, в 10-12 століттях — знову візантійці. В 13 столітті Сугдея стає центром венеціанської колонії, але поступово генуезці витіснили своїх суперників із Криму. В 1365 році вони захопили Солдайю (генуезька назва Судака), а потім і весь південний берег. Більшість будівель Судацької фортеці, що збереглись до наших днів, належать генуезькому періоду, тому її іменують «генуезькою».

У 1475 році на побережжя біля фортеці висадились війська турецького султана. Вони розуміли, що фортеця неприступна, тому вдались до підступу. За допомогою катапульт закидали через стіни фортеці трупи, замасковані під померлих від чуми. Ніхто не насмілювався їх прибирати, в місті почалася паніка. Консул з найманим військом утік морем, а мешканці фортеці вирішили здатися на милість завойовників і відкрили ворота. Того ж дня все населення міста-фортеці було вирізане. Після падіння фортеці Судак і частина Криму ввійшли до складу Оттоманської Порти і керувались турецьким намісником султана.

Після приєднання Криму до Росії тут був розквартирований Кирилівський полк і за наказом Потьомкіна побудовані 2 казарми, руїни яких збереглися. Перед однією залишилось 2 чавунні гармати, покинуті російськими військами як непотріб.

Фортеця стояла століттями. Вона була непідвладна природним стихіям, оскільки камені будівель були скріплені спеціальним розчином, який мав еластичність, тому її стінам не були страшні землетруси. Зруйнували її люди, розтягнувши як будматеріал для своїх будівель.

В 1960-х роках була спроба відновити первісний вигляд фортеці. Було пророблено багато роботи, проте вона не була закінчена. З часом одна зі стін, побудованих радянськими будівельниками, рухнула.