Следующей остановкой стал город Валила. В противоположность Танжеру, о Валиле того времени нам известно многое. Город этот, называвшийся тогда Волюбилис, был при римлянах одним из самых значительных городов Мавритании. Хотя в III веке, за 400 лет до похода Укбы, имперские власти практически устранились из него, он оставался городом, и по крайней мере часть городского центра в нем была еще обитаемой. Большинство населения, вероятно, составляли берберы, и жили они, несомненно, в домах берберской архитектуры, однако могильные плиты VI века сохранили имена и титулы римского типа.
И снова Укба, как нам сообщают, разбил местных берберов и, не задерживаясь, двинулся дальше. Теперь он направлялся к югу через плоское марокканское плато к горам Атласа. По всей видимости, он в погоне за бегущими берберами перевалил горы, дойдя до Вади Дра, после чего вернулся, чтобы осадить город Агмат, стоявший близ нынешнего Мар-ракеша. В городе жили берберы-христиане, и, кажется, его, против обыкновения, Укбе пришлось брать штурмом. Потом он снова углубился в Атласские горы, пройдя перевалами, выводившими в плодородные земли Вади Сус между Высоким Атласом и более сухим хребтом Анти-Атлас. Долина выходит к морю у Агадира. Эти земли арабы назвали Сус аль-Акса, и они стали на ближайшее столетие границей подвластных мусульманам стран.
В противоположность большинству районов, пройденных Укбой, в Вади Сус, кажется, имелось плотное население из берберских племен, живших, как они живут и по сей день, в горных деревушках. Они оказали отряду мародеров упорное сопротивление. Укба одержал несколько побед, и, захватив городок Наффис, якобы основал там мечеть—возможно, скорее как благодарственную жертву за свои победы, чем как место для молений мусульманской общины. В других случаях успех не давался ему, так что для потомков увековечили «кладбища мучеников» как места, где пали в битве его воины. Поход его окончился в Вади Сус, когда Укба вышел к Атлантике. Этот миг попал в легенды. Он якобы въехал в море на коне, пока вода не дошла тому до брюха, и воскликнул: «О Господь! Если бы море не остановило меня, я прошел бы по землям подобно Александру Великому, отстаивая твою веру и сражаясь с неверными!» Образ арабского воина, чей поход во имя Господа останавливают лишь морские воды, остался самым привлекательным и запоминающимся в истории завоеваний.
От западного края континента он вернулся на восток в горы Орес. Здесь он разделил войско, отпустив большую часть воинов по домам. При себе он оставил маленький отряд, с которым намеревался захватить Тубну в Забе. Здесь он встретил большое войско под командованием Косейлы, сбежавшего из заключения в Кайруане. Тот отказался от прежнего союза с мусульманами и снова стал лидером берберского сопротивления. Бой, насколько известно, был коротким и неравным, и Укба в нем приобрел мученичество, которого, судя по всему, добивался.
Поход Укбы на запад остается одним из важнейших мифов об основании мусульманского Магриба. Однако с практической точки зрения он дал довольно скудные результаты. Судя по всему, Укба предпочитал не штурмовать укрепленных городов, уходя вместо этого все дальше на запад через пустынные земли. Возвращаясь, он не оставил гарнизонов в «завоеванных» местах и не установил сбора дани или налогов. Кроме мечети в Кайруане ему приписывают еще закладку двух мечетей в Вади Сус и Вади Дра, но не похоже, чтобы хоть одна из них была прочной и долговечной. Имеется у его подвигов и более зловещая сторона. Он, как известно, забирал живую добычу — молодых берберских девушек, «подобных которым не видели нигде в мире». На рабских рынках Востока за них давали до 1000 динаров. Элита высоко ценила их — матерью великого аббасидского халифа Мансура (754-775) была как раз одна из таких берберских девушек, захваченная примерно в это время. Такая торговля рабами продолжалась первые полвека мусульманского владычества в Северной Африке, и она послужила причиной жестокого озлобления новообращенных мусульман-берберов.
Поражение и смерть Укбы могли привести к тому, что арабов окончательно изгнали бы из Магриба. Его агрессивная экспедиция заставила объединиться против захватчиков большинство крупных берберских племен. Возглавивший их Косейла решился идти на Кайруан. В городе воцарились смятение и отчаяние. Люди собрались в мечети, чтобы решить, что делать. Были среди них такие, как Зухайр ибн Кайс, решивший держаться до конца и говоривший языком шахидов: «ГЬсподь осенил мученичеством ваших друзей, и они вошли в райский сад. Следуйте их примеру!» Другие возражали, что следует отступить в безопасные земли на востоке. Несмотря на воодушевляющие речи о самопожертвовании, большинство оказалось за отступление, и Зухайр, видя, что с ним осталась только его семья, последовал за остальными, остановившись только в своем дворце в Барке.
Победоносный Косейла оккупировал основанный Укбой город. Там он объявил себя «эмиром Ифрикии и Магриба», гарантировал безопасность тем мусульманам, которые захотят вернуться и, поменявшись с ними ролями, собирал с них налоги. Около четырех лет (684-648) Косейла правил в Кайруане, удерживая власть над материковыми землями, в то время как византийцы еще держались в Карфагене, а их флот патрулировал побережье, оказывая поддержку сохранившимся фортам и не позволяя мусульманам атаковать Сицилию.
Отчасти слабость мусульман объясняется хаосом, захлестнувшим халифат после смерти Йазида I в 683 году. Даже после воцарения Омейядского халифа Абд аль-Малика в 685 прошло несколько лет, прежде чем мусульмане собрались с силами, чтобы восстановить свои позиции в Тунисе. В 688 году Абд аль-Малик, находившийся в Сирии, поставил Зухайру, образцового святого воина, возглавить экспедицию из Триполи, которая должна была вернуть Кайруан. Один из источников сообщает, что его войско составляли 4000 арабов и 2000 берберов. Кажется, они добрались до Кайруана, не встретив никакого сопротивления. Косейла, до которого дошло известие об их приближении к городу, предпочел отступить. Город в то время не имел стен и давал плохую защиту. Кроме того, его заботили еще оставшиеся в городе мусульмане, которые могли превратиться в «пятую колонну», и бербер хотел держаться поближе к горам на случай, если дело обернется плохо. Он встал лагерем в местечке под названием Миме на краю гор Орес. Здесь он и потерпел поражение от войска Зухайры, и сам был убит. Как часто бывает, нам трудно понять причину успеха мусульманского войска, выступавшего, вероятно, против превосходивших его сил, хорошо знакомых с местностью. Мы можем лишь в очередной раз отметить, что, когда доходило до решающих сражений, мусульмане брали верх.
Хотя византийцы, по-видимому, не оказали Косейле никакой военной помощи в последнем бою, их флот на средиземноморском побережье все еще представлял силу, с которой следовало считаться. Теперь они нанесли удар, предназначенный, кажется, чтобы отвлечь внимание мусульман на Киренаику, и Зухайр, проповедовавший аскетическое отвращение к политической власти, вынужден был повести своих людей на восток против новой угрозы. Он обнаружил, что византийцы оккупировали Барку, остававшуюся в руках мусульман уже полвека со времени первой экспедиции Амра ибн аль-Аса. При попытке выбить их из города он пал как мученик, а его маленькое войско было разбито.
Шбель Зухайра в Барке оказалась низшей точкой в усилиях мусульман отвоевать Северную Африку. Дальше дела пошли на подъем. К 694 году энергичный и способный омейядский халиф Абд аль-Малик разгромил всех своих многочисленных врагов на землях ислама. Теперь у него появились свободные войска, которым, чтобы сохранить их верность, пошел бы на пользу поход за добычей. Были и другие веские причины для возобновления кампании в Северной Африке. Пока Киренаика была в руках врага, Египет тоже оставался под угрозой. Кроме того, мусульмане никогда не уступали контроля над однажды захваченными землями: тот, кто претендовал на титул военачальника правоверных, не мог допустить такого, не встретив сильного сопротивления.
