В трудах местного летописца Мирзы—Хедир Везирова (XIX в.) основание Дербента приписывается шаху Лехрасибу из династии Каянидов — современнику библейского царя Соломона. Древнегрузинская хроника повествует о страшном нашествии хазар, для усмирения которых по приказу персидского царя Афридона полководец Ардом вошел с большим войском в страну хазар, разбил их, «воздвиг город у морских ворот и назвал его Дарубанди, что в переводе означает „замкнул ворота“».
Существует и легенда, в которой говорится, что Дербент основал Александр Македонский. Он воздвиг между морем и горами стену с башнями, которую запер окованными железными воротами, «чтобы люди, жившие по ту сторону, не смогли причинить ему никакого вреда». Великий полководец древности никогда не был в этих местах, однако уже само существование многочисленных легенд говорит о том значении, какое имели Дербентский проход и возведенная там система укреплений.
Оборонительный комплекс Дербента условно можно разделить на три части, цитадель Нарын-кала, морские стены и Даг-бары (горная стена). Каждое укрепление могло функционировать самостоятельно, и в то же время они являются частями единой оборонительной системы Ядром ее является Цитадель Нарын-кала, которую сначала возводили из сырцового кирпича. Ее крепостные стены сохранились почти полностью, хотя именно они более всего подвергались переделкам, особенно в позднее время (XVII–XIX в.в.)
Холм, на котором расположена цитадель, на северной стороне имеет круглые склоны — в сторону оврага, а на востоке — в сторону города. Южный и западный склоны холма более пологие. Общая протяженность стен Нарын-калы достигает 700 метров, а толщина их равняется 2 метрам. В плане цитадель имеет форму неправильного многоугольника, все выступы ее глухие: два из них имеют внутренние лестницы, по которым поднимались на стены. С восточной и северной стороны выступов меньше, так как неприступными эти стороны цитадели делает крутой склон холма.
Южная сторона цитадели, где нет естественных преград, укреплена сильнее, чем северная. Стена здесь значительно выше (местами достигает в высоту 20 метров) и мощнее, с множеством выступающих квадратных фортов. Мощные стены с бойницами, глубокое ущелье с крутыми склонами, опоясывающими цитадель с 3 сторон, система водохранилищ для больших запасов воды — все делало Нарын-калу почти неприступной.
О названии цитадели легенды и предания рассказывают разное. В одних из них говорится, что шах назвал ее именем любимой жены Нарын, что означает «нежная, изящная». В других повествуется, что название закрепилось за цитаделью из-за ее размеров: слово «нарын» еще имеет значение «маленькая, компактная». Третьи предания утверждают, что на территории цитадели росло много померанца («нарынч») и первоначально цитадель называлась «Нарынч-кала», а потом последняя буква утратилась.
Из-за довольно крутого холма, на котором расположена Нарын-кала, все четыре ее внутренних двора размещаются на разных уровнях в виде искусственно выровненных террас с системой подпорных стен. В надвратной части входа в цитадель находились Диван-хана (ханская канцелярия и судилище) и приемная, возведение которых относится к XVII веку.
У северной стены цитадели, позади ханского дворца, размещался «Зинт дан» — подземная тюрьма («каменный мешок»). Легенды и предания многое рассказывают об ужасах этого мрачного сооружения, прозванного в народе «Гедян гяльмяз» («вошедший не вернется»). Некоторые ученые считают, что первоначально это было одно из древних водохранилищ, впоследствии приспособленное под тюрьму.
К древним сооружениям цитадели относится и огромный, в плане квадратный резервуар, который перекрыт куполом, стоящим на четырех арках. Внушительные размеры резервуара отличают его от остальных древних водохранилищ Дербента, которые к тому же имеют прямоугольную форму. Необычная для мусульманского Востока крестообразная форма резервуара дала некоторым ученым основание предположить, что его строителями были византийские мастера-христиане. По другим версиям под водохранилище приспособили христианский храм раннего Средневековья. Однако крестообразная форма характерна не только для христианских сооружений, так как по древним поверьям горцев крест олицетворял «все четыре стороны света» и потому часто использовался как знак-оберег.
Одно из самых маленьких водохранилищ Нарын-калы — тоже квадратное (2,65x2,65 м) и тоже перекрыто куполом. Оно расположено у входа в цитадель, и легенды рассказывают, что водой из него пользовались только хан и члены его семьи. У резервуара постоянно стоял вооруженный слуга, который, кроме охраны водоема, первым должен был пить воду, прежде чем ее поднесут хану или члену его семьи.