A son arrivée en Egypte, Muslama fit choix d’un de ses Mawâlî nommé Dinar et surnommé Abu al-Muhajir, pour être son Khalifa dans la province d’Afrique. Ceci eut lieu en l’an 55/675. Le nouveau gouverneur se rendit à sa destination ; mais, ayant de la répugnance à se fixer dans la ville fondée par ‘Uqba, il alla camper à 2 milles de là, et y traça les fondations d’une autre ville, afin de perpétuer le souvenir de son nom et de rendre inutile l’ouvrage de son prédécesseur. Cette nouvelle ville fut nommée par les Berbers Bi-Gayrawan. Quand la construction en fut commencée, il ordonna qu’on détruisît la ville de ‘Uqba, et celui-ci en fut tellement indigné, qu’il se rendit auprès du khalifa Mu‘awiya, et lui adressa ces paroles :

« C’est pour toi que j’avais attaqué et subjugué cette province ; j’y ai bâti des mosquées, établi des lieux de halte, et donné au peuple des domiciles fixes ; et tu viens d’y envoyer un esclave des Ansars qui m’a remplacé en m’insultant ! »

[…]

‘Uqba parvint cependant à repousser l’ennemi, et, l’ayant poursuivi jusqu’à la porte de la forteresse, il lui enleva beaucoup de butin. Comme il ne voulait pas s’arrêter (pour bloquer la place), il partit pour le pays du Zab, et là il demanda quelle était la ville principale ; on lui désigna la ville d’Arba, où le chef résidait, et qui servait de point de réunion aux princes du Zab : elle était entourée de 360 villages, tous très peuplés.

[…]

De là ‘Uqba se dirigea vers Tahurt ; les Romains ayant été prévenus de son dessein, demandèrent et obtinrent le secours des Berbers. Alors ‘Uqba fit halte, et, s’adressant à ses troupes, il les excita au combat. Dans l’action qui s’ensuivit, les Romains et les Berbers ne purent résister aux musulmans ; ils perdirent beaucoup de monde en peu de temps, et les troupes grecques évacuèrent la ville.

‘Uqba vint ensuite camper près de Tanger, et un Romain nommé Ilyân qui tenait un haut rang dans son peuple, vint à sa rencontre, et eut l’adresse de se le concilier en lui offrant de beaux cadeaux et en se mettant entièrement à ses ordres. ‘Uqba le questionna relativement à la mer d’Espagne, et ayant appris qu’elle était bien gardée, il lui dit :

« Dirige-moi où je puisse trouver des hommes parmi les Romains et les Berbers

-Quant aux Romains, répondit Julien, tu les a laissés derrière toi ; mais devant toi sont les Berbers et leurs cavaliers ; Dieu seul en sait le nombre

-Où se tiennent-ils ? demanda ‘Uqba.

-Dans as-Sus al-Adna, répondit l’autre ; c’est un peuple sans religion ; ils mangent des charognes, ils boivent le sang de leurs bestiaux, et ils sont comme des brutes, car ils ne croient pas en Dieu, et ils ne le connaissent même pas. »

Sur cela, ‘Uqba dit à ses camarades : « Marchons avec la bénédiction de Dieu ! »

De Tanger il se dirigea du côté du midi, vers as-Sûs al-Adna, et il vint jusqu’à une ville nommée Taroudant. Là il rencontra les premières troupes berbères, et il en fit un grand carnage : le reste prit la fuite, et sa cavalerie se détacha à leur poursuite et pénétra dans as-Sus al-Adna.

Les Berbers se réunirent alors en nombre si grand que Dieu seul pouvait les compter ; mais ‘Uqba les attaqua avec un acharnement inoui. Il en fit un grand massacre, et s’empara de quelques-unes de leurs femmes, lesquelles étaient sans pareille : on rapporte qu’une de leurs jeunes filles, qui avait été amenée en Orient, fut estimée à environ 1000 mithqal.

Ayant continué sa marche, il vint jusqu’à la Mer Océane, sans avoir éprouvé de résistance, et il entra-dans la mer jusqu’à ce que l’eau atteignît le poitrail de son cheval : levant alors la main vers le ciel, il dit :

« Seigneur ! si cette mer ne m’en empêchait, j’irais dans les contrées éloignées et dans le royaume de Dhu al-Qarnayn, en combattant pour ta religion, et tuant ceux qui ne croient pas à ton existence ou qui adorent d’autres dieux que toi. »

S’adressant ensuite à ses camarades, il leur dit :

« Retournons sur nos pas avec la bénédiction de Dieu. La terreur des infidèles était devenue si grande qu’ils fuyaient les pays que l’armée traversait, et l’expédition se dirigea vers la province d’Afrique. »

De là il se rendit à Tubna, petite ville à 8 journées de Qayrwan, et dans l’assurance que le pays tout entier était soumis, et qu’il n’y avait plus d’ennemi digne d’être craint, il ordonna à ses troupes de se rendre successivement, par détachements, à Qayrwan.

Il se dirigea ensuite vers Tahuda et Badis pour en faire la reconnaissance, et pour voir combien il faudrait de cavalerie pour bloquer ces 2 villes. Il y laissa les hommes nécessaires pour cet objet, et les Romains, le voyant avec un petit nombre d’hommes, fermèrent les portes de leurs châteaux et lui lancèrent des flèches, des pierres et des malédictions : pour lui, il les appelait à Dieu.