Начиная с 640 года арабы периодически опустошали Аомению, Грузию и Кавказскую Албанию, пока эти страны не признали свое поражение и не отдались под протекторат халифата. Арабы воевали настолько хорошо, что среди хазар, если верить Ибн ал-Асиру, распространилось мнение, что «эти люди не подвержены смерти». Историк пишет: «…Мусульмане совершали еще несколько походов (против хазар), однако никто из них не был убит, и поэтому они (хазары) подумали, что они (мусульмане) не умирают». Впрочем, нашлись среди хазар и скептики. «“Не попытаться ли нам (убить их)”, — сказали некоторые из них, и они устроили им (мусульманам) засаду в лесу, а когда некоторые (мусульманские воины) прошли мимо засады, в них пустили стрелы и убили их». Вероятно, результаты этого эксперимента воодушевили хазар, и с тех пор их войны с арабами шли с переменным успехом.

В 654 году арабы завоевали Азербайджан, который до тех пор входил в состав Персии. Под их властью оказался и Дербент. Персидский комендант города сдал крепость, попросив сохранить за ним должность и избавить жителей от налогов. Арабы согласились и сдержали слово, но ничего хорошего для жителей Дербента из этого не получилось: крепость стала военной базой халифата для набегов на земли хазар. Ее персидский комендант тщетно отговаривал завоевателей от продвижения на север, уверяя, что он не для того решил дело миром с арабами, чтобы навлечь на себя новых врагов.

Действительно, после этого многострадальный Дербент стал переходить из рук в руки. Хазары и арабы сменяли здесь друг друга каждые несколько лет в течение всей второй половины VII и начала VIII века. В 713 году арабы в очередной раз взяли город, в котором стоял трехтысячный хазарский гарнизон, — им помогла измена одного из жителей, который показал им ведший в крепость подземный ход. Арабы вырезали население города и разрушили крепостные стены и башни, потому что понимали: Дербента им не удержать.

Армянский историк VIII века Гевонд (ошибочно относящий это событие к 717 году, к правлению халифа Сулеймана) пишет:

«На втором году своей власти Сулейман собрал многочисленное войско, поручил его военачальнику своему Мслиму (Маслама, внебрачный сын халифа Абд аль-Малика. — Авт.), и отправил его к воротам каспийским. Достигши места своего назначения, (войска Исмаила) сразились с войсками гуннскими, занимавшими город Дербент. Они разбили (Гуннов) и прогнали их, разрушивши стены и башни крепости».

По сообщению Гевонда, разрушая крепость, арабы нашли в ее основании камень с начертанной на нем надписью: «Маркиан, самодержавный император, выстроил город и твердыню эту, истратив на это много талантов из сокровищ своих. Впоследствии сыны Исмаила разрушат их и возобновят на свои сокровища». Арабы поверили и сообщению о строительстве крепости византийским императором середины V века Маркианом, и пророчеству, хотя оно и было сделано христианами. После чего они «перестали разбивать стены и, набрав каменщиков, снова выстроили разрушенную стену».

В том, что крепость была построена императором Маркианом, есть рациональное зерно. Хотя первые укрепления появились на месте Дербента еще в VIII веке до н.э., крепость неоднократно перестраивалась, в том числе при персах. В середине V века принадлежала она, безусловно, последним, но Византия, которая в те годы находилась с Персией в самых дружеских отношениях, неоднократно финансировала их оборонительные сооружения — они сдерживали натиск кочевников, угрожавших в том числе и самой Византии. Поэтому Маркиан вполне мог участвовать в строительстве дербентских укреплений — по крайней мере деньгами.

Значительно менее вероятным представляется сделанное им пророчество, хотя бы потому, что в его времена никакого Арабского халифата еще не было. Тем не менее Маслама отстроил им же разрушенные стены Дербента. Правда, по сообщениям других авторов, он сделал это только в тридцатые годы VIII века, когда арабы окончательно укрепились в городе и почувствовали, что их войны с хазарами близятся к победному завершению.