L’influence byzantine demeurera à Alger jusqu’à la fin du 7ème siècle, avant que les forces arabes musulmanes conquièrent la ville en 698. Cette conquête introduisit l’islam en 710.

En 950, Ziri ibn Menad affronte et bat les kharidjites (une branche « dissidente » de l’islam). Il fonda la ville d’Achir non loin de l’actuelle ville d’Alger, qui sera pendant un certain temps la capital de sa dynastie (dynastie des Zirides jusqu’en 984).

Bologhine ibn Menad fonda vers 960 la Casbah d’Alger, qui est aujourd’hui le cœur historique de la ville et un quartier inscrit au patrimoine mondial de l’humanité de l’UNESCO. Il servait de base comme de débouché maritime pour la jeune capitale qu’est Achir (étant un peu plus reculé dans les terres). En 1097, la Grande Mosquée d’Alger fut construite par Youssef ibn Tachfin (un leader politique et militaire berbère, fondateur de la dynsatie des Almoravides ayant unifié une grande partie du Maghreb et de l’Espagne musulmane).