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