Известно, что государство арабов возникло в VIIв. Его создание связано с именем пророка Мухаммеда, сумевшего путем распространения новой религии (ислама) объединить племена Аравийского полуострова в могущественное государство. С 40-х годов VII в. начинается полоса арабских походов на Кавказ, в Туркестан, Малую Азию и Северную Африку.

В VII-VIII веке ислам приходит в Дагестан. Этот период известен 150-летней войной горных албанов с арабами и хазарами. В 636 году албанский князь Джеваншир возглавлял своё войско против арабов в битве при Кадисии. Историк Каганкатваци М. пишет что в награду за участие в сражении с арабами, последний сасанидский царь Йездигерд III опоясал Джеваншира золотым поясом унизанным жемчугом, навесил меч, дал ему браслеты на руки и прекрасный венец на голову. После падения государства Сасанидов, Джеваншир нанес ряд поражений стоявшим в Албании персидским войскам и освободил захваченный персами Партав.

В 641 году арабы захватили Дербент. В 660 году Джеваншир, царь Албании (638-670), был в союзе с Византией. В 662 году хазары вторглись на территорию Кавказской Албании. Правитель Джеваншир отбил это нападение, затем заключил перемирие с хазарами и взял в жены дочь хазарского кагана. В 667 году, ввиду хазарских набегов, Джеваншир ездил в Дамаск к халифу Муавию I, чтобы заключить военный союз против хазар. Халиф признал Джеваншира правителем всей Кавказской Албании, но только как своего наместника, и в знак почтения подарил Джеванширу хорошо обученного слона, привезенного из Индии, булатный меч в золотых ножнах, кафтан усыпанный перлами, кресты позолоченные, попугая, превосходнейшую из всех птиц, и также пятьдесят две быстроногие лошади. В 670 году, в заговоре албанских князей, Джеваншир был убит. Джеваншир ознаменовал себя как выдающийся правитель Кавказской Албании, воевал против персов, хазар и арабов, заключая со своими противниками тактические союзы. В 684 году хазары вновь напали на Албанию. В 685 году последующий царь Албании, Вараз-Тиридат, отправил своего представителя к хазарам в Варачан, в ставку Алп-Илитвера, и заключил мир.

В 705 году Маслама ибн Абдул-Малик, брат халифа Валида I, захватил Дербенд.

В 722 году халиф Язид II отправил Джарраха ибн Абдаллаха ал-Хаками на зашиту дербентской крепости. В 723 году арабские войска под командованием Джарраха продвигаются через территорию Дагестана и захватывают Беленджер. В 730 году Джаррах был убит в битве при Ардебиле.

В 733 году Маслама ибн Абдулмалик наилучшим образом укрепил Дербент, построив там семь железных ворот, и пошел с войском на Кумух. Правители Кумуха вели кровопролитные бои, где арабы одержали победу.

В 737 году под натиском хазар территория Дагестана отошла от власти арабов.

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

Арабы не смогли удержаться в Кумухе, из-за начавшейся в 745 г. гражданской войны в Халифате.

Согласно работам А. К. Бакиханова, жители Кумуха приняли ислам в период походов Масламы, который назначил кадия для обучения жителей обрядам новой веры. В 777 году было завершено строительство первой соборной мечети в Кумухе, самой большой в Дагестане в этот период. В «Дербент-наме» пишется что полководец Маслама передал управление территорий правителю Кумуха который был старшим властителем всего Дагестана, и чтоб ему были подвластны все вилаяты вплоть до границ Гурджистана. В VIII веке, как пишет Шихсаидов, «Шамхал стал правителем и вали над всем Дагестаном» . Мухаммед Рафи в «Тарих Дагестан» пишет что «этот правитель стал брать доходы со всех владений, вилаятов и областей. Имя этого правителя было Шамхал». В эти территории Кумухского шамхала входили следующие княжества: Хамры, Кюра, Куба, Гулечан, Курах, Ахты, Хнов, Рутул, Захур, Кумук, Авар, Карах, Гидат, Тарки, Агран и Андри, что представляло большую часть Дагестана. Это дагестанское государство во главе с лакским царём несомненно являлось албанским союзом времён Ануширвана.