Ibn-Bahdal se mit en route, mais avec une suite peu nombreuse pour ne pas éveiller de soupçons, et parce qu'il était sûr de trouver des soldats partout où il rencontrerait des contribules. Arrivé auprès des Beni-Abd-Wadd et des Beni-Olaim, deux sous-tribus de Kelb qui demeuraient dans le Désert, au sud de Douma et de Khabt, il leur communiqua le projet de Khâlid, et, les hommes les plus braves et les plus déterminés de ces deux tribus lui ayant déclaré qu'ils ne demandaient pas mieux que de le suivre, il s'enfonça avec eux dans le Désert, après leur avoir fait jurer qu'ils seraient sans pitié pour les Caisites.
Un homme de Fazâra, sous-tribu de Cais, fut leur première victime. Il sortait d'une riche et puissante lignée; son bisaïeul, Hodhaifa ibn-Badr, avait été le chef des Dhobyân dans la célèbre guerre de Dâhis; mais comme il avait le malheur d'avoir pour mère une esclave, ses fiers contribules le méprisaient à un tel point qu'ils avaient refusé de lui donner une de leurs filles en mariage (ce qui l'avait obligé à prendre femme dans une tribu yéménite) et que, ne voulant pas l'admettre dans leur société, ils l'avaient relégué aux lisières du camp. Ce malheureux paria récitait à haute voix les prières du matin, et c'est ce qui le perdit. Guidés par sa voix, les Kelbites fondirent sur lui, le massacrèrent, et, joignant le vol au meurtre, ils s'emparèrent de ses chameaux, au nombre de cent. Ensuite, ayant rencontré cinq familles qui descendaient aussi de Hodhaifa, ils les attaquèrent. Le combat fut acharné et se prolongea jusqu'au soir; mais alors tous les Caisites gisaient sur le champ de bataille et leurs ennemis les croyaient morts. Ils ne l'étaient pas cependant; leurs blessures, quoique nombreuses, n'étaient pas mortelles, et, grâce au sable qui, poussé par un violent vent d'ouest, vint les couvrir et arrêter l'écoulement de leur sang, ils échappèrent tous à la mort.
Continuant leur route pendant la nuit, les Kelbites rencontrèrent, le lendemain matin, un autre descendant de Hodhaifa, nommé Abdallâh. Ce vieillard était en voyage avec sa famille; mais il n'avait auprès de lui personne en état de porter les armes, excepté Djad, son fils, qui, dès qu'il vit arriver la bande kelbite, prit ses armes, monta à cheval et alla se placer à quelque distance. Quand les Kelbites eurent mis pied à terre, Abdallâh leur demanda qui ils étaient. Ils répondirent qu'ils étaient des dîmeurs envoyés par Abdalmélic.
—Pouvez-vous me montrer un ordre à l'appui de ce que vous dites? demanda le vieillard.
—Certainement, lui répondit Ibn-Bahdal, cet ordre, le voici;—et il lui montra un diplôme revêtu du sceau califal.
—Et quelle est la teneur de cet écrit?
—On y lit ceci: «De la part d'Abdalmélic, fils de Merwân, pour Homaid ibn-Bahdal. Au dit Homaid ibn-Bahdal est ordonné par la présente d'aller lever la dîme sur tous les Bédouins qu'il pourra rencontrer. Celui qui paiera cette dîme et se fera inscrire sur le registre, sera considéré comme sujet obéissant et fidèle; celui au contraire, qui refusera de le faire sera tenu pour rebelle à Dieu, à son Prophète et au commandeur des croyants.»
—Fort bien; je suis prêt à obéir et à vous payer ma dîme.
—Cela ne suffit pas. Il faut faire autre chose encore.
—Quoi donc?