Aroudj avait été pris par les galères de Rhodes et la tradition veut que plus tard, lorsqu'il régna à Alger, il se soit souvenu de l'organisation militaire des chevaliers. Parvenu à s'évader, il se rendit à Tunis, où il fut bien reçu par le souverain hafside; bientôt rejoint par son frère Kheir-ed-Din, il se créa une principauté indépendante dans l'île de Djerba. Ses succès amenèrent sous ses ordres un grand nombre d'aventuriers; le sultan de Tunis était leur recéleur et leur complice; en une fois, ils lui offrirent cinquante jeunes Espagnols tenant des chiens en laisse, des oiseaux rares et quatre jeunes filles nobles parées de beaux vêtements et montées sur de beaux chevaux.

Les Kabyles de Bougie vinrent de­mander secours à Aroudj contre les Espagnols; il attaqua la place à diverses reprises, mais il eut le bras emporté par un boulet et dut finalement lever le siège. Malade et découragé, il se retira à Djidjelli, où les habitants d'Alger allèrent à leur tour solliciter son intervention, lui demandant de détruire la forteresse espagnole, l'odieux Pefion, qui les empêchait de faire la course et qui était « comme une épine plantée dans leur cœur ». Aroudj envoya par mer seize bâtiments, sur lesquels il embarqua la moitié de ses Turcs avec son artillerie et son matériel, et se mit en route en suivant la côte à la tête du reste de ses soldats, au nombre de 800, et d'un contingent d'environ 5 000 auxiliaires kabyles. Aroudj ne prit pas le Pefion, que ses boulets ne purent atteindre, mais se rendit maître d'Alger, après avoir de ses propres mains égorgé dans son bain Salem-et-Teumi, chef de la tribu des Thaleba qui dominait dans la Mitidja. Les Turcs le proclamèrent roi et les indigènes, auxquels plaisait son énergie, le soutinrent vigoureusement; ses soldats se chargèrent d'ailleurs d'assouplir la population. Une expédition de secours, envoyée d'Espagne sous la conduite de Diego de Vera, échoua dans une tentative pour s'emparer d'Alger et se rembarqua au bout de trois jours sous une tempête furieuse (1516). Aroudj conquit ensuite la vallée du Chélif, livra combat aux Mehal dans l'Oued­Djer, se rendit maître de Médéa et de Ténès, dont le chef fut empalé. Un parti nombreux l'appelait à Tlemcen, ensanglantée par les querelles des princes zeiyanites. Aroudj intervint dans ces querelles, entra en vainqueur dans la vieille capitale de Yaghmoracen et fit noyer tous les princes zeiyanites dans un grand bassin qui servait à donner des fêtes nautiques.