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

Наконец наступила развязка, своего рода повторение истории Хусейна и Мусаба. Абдулла, с горсткой приближенных, вырвался наружу через проделанную неприятелем брешь в стене, чем озадачил даже своих врагов. Он срубил голову одного из завоевателей. Крик «Аллах Велик!» раздался со стороны войска Хеджаджа, что должно было подтвердить, что Абд-эль-Мелик — неоспоримый халиф ислама и что города Мекка и Медина утратили всё свое былое значение.

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

В 695 году восстание в далеком Хорасане вынудило Абд-эль-Мелика послать на восток сильную личность. Хеджадж был правителем Ирака, он отправился в Куфу, вошел туда стремительно, во главе огромного войска. Направился прямиком к мечети, встал у амвона и объявил трепещущим людям, что пришел заставить «злодея нести тяжесть содеянного», что перед собой он видит «головы, созревшие для жатвы, тюрбаны и бороды, обагренные кровью».

«Рабы мятежа и коварства, я не из слабых. Я обдеру вас, как с деревьев снимают кору. Я высеку вас кнутом, как секут верблюда, отставшего от стада. Я раздроблю вас в крошку, как дробят щебень у дороги. Я Хеджадж, сын Юсу- фа! Когда я бреюсь, то задеваю кожу!»

В Басре он произносил подобные речи, от которых число его противников только росло. Но он их быстро успокоил, чего, собственно, от него и ждал хозяин. Подобным образом он одолел и мятежного наместника Хорасана, передав весь регион под власть халифа. Именно в этот период Хеджадж основал город Васит, расположенный на полпути от Басры в Куфу, чтобы ему было легче оттуда руководить ситуацией в регионе (ок. 702 г.).

В то же время фанатичные хариджиты взбунтовали огромную территорию внутри халифата. Своими отчаянными действиями они причиняли постоянно беспокойство Абд-эль-Мелику и его наместникам. Они оказались самыми свирепыми и непримиримыми врагами, каких только Хеджаджу приходилось видеть. Но в свое время удалось справиться и с ними. Последний их вожак — Шебиб, побеждавший Хеджаджа в нескольких битвах, утонул во время отступления, после стычки, во время которой его армия была разбита. После гибели Шебиба установился мир во всех владениях Абд-эль-Мелика. Спокойствие продолжалось целых пять лет (с 696 г.)

Царствование Абд-эль-Мелика ознаменовано тем, что появились первые сарацинские монеты. Время выплаты дани Константинополю подходило к концу, и этот халиф отказался платить в монетах империи. Аравия, Сирия, Ирак — все зависели от Персии и Византийской империи, пользуясь ее деньгами. Когда Абд-эль-Мелик впервые попытался расплатиться арабскими монетами, монарх отказался их принять. Тогда халиф отказался платить в какой- то иной форме, а будучи одним из сильнейших правителей в мире, он мог настаивать на своем отказе и тем самым добиться еще большей независимости.

Пока продолжались войны между халифом Дамаска и Мекки, жители Африки, которые прежде искали покровительства сарацин, отказались от обязательств. Абд-эль-Мелик, как только собрался с силами, попытался призвать их к порядку и послал на запад армию под командованием Хасана (692 г.). Она прошла вдоль северного побережья до Каирвана, далее к Карфагену, подчиненному после долгой осады (жители разбежались кто в Андалусию, кто на Сицилию). Берберов этого региона подчинить было не так просто, но в конце концов они сдались и вся территория оказалась в подчинении халифа.

Проводники отвели сарацин в горы на юго-запад от Карфагена. Там у берберов было стойбище, которым правила царица Кахина (698 г.). Произошла суровая битва, и, хотя многие факты сомнительны, царица была в результате схвачена и обезглавлена в присутствии сарацинского военачальника. Но дело не было закончено, пока африканцы не опустошили сами всю территорию от Триполи до Гибралтарского пролива. 12 тысяч берберских воинов влились в армию сарацин, в Дамаск из покоренных городов полились многочисленные трофеи. Так в третий раз сарацинами была захвачена Африка, но их главенство и на этот раз было вскоре свергнуто, причем греческое население было бы даже радо вернуть арабов, дабы те защитили их от варварских вождей, чье правление оказалось попросту невыносимым.

Правление этого мощного халифа завершилось в 705 году, и на его место пришел старший сын Валид, с которым слава династии достигла вершины.

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

Когда Валид подхватил бразды правления, выпавшие из рук покойного, он, что вполне естественно, решил продолжать наиболее успешные, с его точки зрения, направления отцовской политики. Сам он был из тех, кто неравнодушен к роскоши, человек утонченного вкуса, в том смысле как тогда понимался «вкус», и ему доставляло удовольствие возводить грандиозные здания, украшая их со свойственным восточной архитектуре размахом. Он явно стремился оставить после себя такие памятники, чтобы слава о нем продолжилась в веках. И в этом он преуспел.

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