Aroudj se rend à l'appel de son nouvel allié ; il dresse une batterie à cinq cents pas de la forteresse espagnole qu'il canonne pendant un mois sans pouvoir l'entamer, se crée des partisans parmi la populace, intrigue, conspire, fait étrangler Eutemi et se proclame souverain d'Alger. Aussitôt après, il forme, avec une horde d'aventuriers venus de tous pays, une milice à laquelle il donne une organisation spéciale : les membres seuls de cette milice peuvent concourir aux emplois ; à l'exception des renégats étrangers, nul ne peut en faire partie s'il n'est originaire de Turquie ; enfin, pour mieux soustraire la troupe aux influences locales, les fils mêmes des miliciens en sont exclus s'ils sont nés à Alger.

Son gouvernement (odjac) ainsi constitué, le corsaire-roi, que son frère Kheir-ed-Dine est venu rejoindre, ravage la Mitidja, s'empare successivement de Ténès, de Médéa, de Miliana, puis de Tlemcen (1518). Les troupes espagnoles viennent l'assiéger dans cette dernière ville. Pressé par l'ennemi et manquant de vivres, Aroudj se décide à fuir, un soldat l'atteint sur les bords du Rio-Salado, disent certains historiens, sur ceux de l'Oued-Isly, disent quelques autres, et lui tranche la tête.

Kheir-ed-Dine lui succède : en politique habile, il fait au sultan de Constantinople hommage de sa principauté, et se reconnaît volontairement tributaire de la Sublime-Porte. Le Grand Turc accepte avec empressement ; il nomme Kheir-ed-Dine gouverneur de la province d'Alger sous le titre de Dey et lui expédie en toute hâte 2,000 hommes de ses meilleures troupes. De cette époque date la prise de possession d'Alger par les ottomans, et le même fait qui s'était produit en Asie va se reproduire en Afrique : les Turcs se substitueront aux Arabes comme défenseurs de l'Islamisme.

De l'avènement de Kheir-ed-Dine à la conquête d'Alger par une armée française, la Régence n'a pas d'autre histoire que celle de sa milice.

L'odjac se soustrait peu à peu à la tutelle du Grand Turc et se transforme en une république militaire. La milice, formée des janissaires et des reïss, est souveraine et maîtresse. C'est elle qui élit les deys, et qui les détrône, quand elle ne les assassine pas. Les janissaires contiennent les Arabes et pillent les tribus ; les reïss promènent impunément leur pavillon de Gilbraltar à l'Archipel, désolent le littoral et capturent tous les navires qu'ils rencontrent. Telle était l'importance des prises, qu'à la fin du dix-septième siècle on comptait 30,000 prisonniers chrétiens dans les différentes parties de la Régence.

L'Espagne, la France, la Sicile et l'Angleterre tentent inutilement, et à plusieurs reprises, de faire cesser ce brigandage: les Espagnols sont chaque fois repoussés avec des pertes énormes ; les Français et les Anglais bombardent et incendient Alger, mais toujours et en moins de quelques mois, la ville est rebâtie et sa marine reconstituée. Précisons :