Selon la tradition, c‘est au onzième siècle de l'ère chrétienne que les populations actuelles sont arrivées dans la vallée du M'zab. Chassées par les Fatimides de la ville de Tihert (Tiaret) où elles résidaient auparavant, les tribus ibadites avaient erré longtemps dans le désert avant de se fixer dans ce qu'on appelait alors la vallée de Timizert (ancien nom du M'zab). Cette vallée n'était pas déserte puisque des populations y vivaient déjà, dans des villages dont la tradition garde encore quelques noms et les nouveaux venus ont su vivre avec elles et, ensemble, construire ce qui allait devenir la civilisation des cités. El Atteuf – qui s'appelle Tajnint dans le dialecte berbère local – est la première de ces cités. Toujours selon la tradition, elle aurait été fondée en 1011 ou 1012 de l'ère chrétienne, par un cheikh appelé Abghur qui venait d'une vallée appelée Daya. Ce cheikh et sa fraction ont été rejoints par les habitants de trois villages qui existaient dans la région et ensemble, ils ont constitué la nouvelle ville de Tajnint ; après Tajnint, c'est au tour de Bounoura d'être fondée, en 1019, où selon certaines sources, un peu plus tard, vers 1046. Ghardaïa, qui est aujourd'hui la capitale du M'zab, fut fondée vers 1058. Puis, c'est Beni Izguen, en 1347. Les deux autres villes qui ont été créées en dehors de la vallée, sont Guerara en 1630 ou 1631 et Berriane, la plus récente des cités, en 1690.
