La regione, un tempo frequentata da berberi nomadi zeneti (wasiliti), ha cominciato ad essere abitata da sedentari nell'XI secolo, quando vi si stabilirono gli ultimi ibaditi superstiti dopo il crollo dell'imamato di Tahert ad opera dei Fatimidi (X secolo). In precedenza l'ibadismo aveva a lungo dominato nell'Africa settentrionale durante l'epoca rustumide.

Dopo essersi rifugiati in alcune oasi vicine, come Ouargla e Sedrata, essi vennero scacciati anche da queste località ad opera degli Almoravidi prima e degli Almohadi poi, decidendo quindi di crearsi ex novo una sede facilmente difendibile in un luogo fino ad allora inospitale e privo di insediamenti stabili: lo Mzab. Qui essi fondarono, una dopo l'altra, le sette città che ancor oggi vi si trovano. Si tratta nell'ordine di:

El-Atteuf (1012), berb. Tajnint ("Avvallamento") o At Takhsait ("Quelli della zucca", gergale); Melika (1017) berb. At Mlishet (i primi insediamenti riguardarono Agherm wadday "la città bassa", alla base della collina dove si trova la città attuale); Bou-Noura (1046), berb. At Bunur o At Wirzu (gergale); Ghardaia (1046), berb. Tagherdayt; Béni-Isguène (1321), berb. At Yijden (pronuncia locale) o At Yizgen (pronuncia degli altri mzabiti), oppure (gergale) At Idis "quelli del fianco" (il nucleo originario, nella parte alta della città, si chiamava Tafilalt); Guerrara (1631), berb. Tamurt n Tefza ("paese dell'arenaria"); Berriane (1690), berb. At Ifragh (gergale).

Le ultime due città, fondate qualche secolo dopo i primi insediamenti, si trovano a una certa distanza da essi, rispettivamente a 100 e a 45 km verso nord.

Lo Mzab venne posto sotto il protettorato francese il 29 aprile 1853, e, dopo la repressione di una rivolta, fu definitivamente annesso il 1º novembre 1883 dalla Francia come parte delle sue colonie nordafricane. Dopo l'indipendenza algerina del 1962 il territorio divenne parte dell'Algeria.