Certains attribuent la fondation de la mosquée à Obeid-Allah Ibn Al-Habhab, gouverneur omeyyade d’Ifriqyia de 734 à 741. D’autres pensent que c’est Hassen Ibn Noomane Al-Ghassani qui a entrepris la construction de la Zitouna. Ibn Noomane prit Tunis en 698/699 sur ordre du Calife Abd-Al-Malik Ibn-Marwane après les révoltes amazighes et juste avant de battre la Kahena en 701. La mosquée aurait été construite pour que les soldats puissent accomplir leurs rites. Mais sa construction se fit en plusieurs étapes et sur plusieurs siècles où elle connut plusieurs extensions et restaurations.

Beaucoup de légendes circulent autour de l’appellation de la mosquée. Et si l’on attribue parfois le nom à la présence d’un olivier sur le lieu de construction du monument, il semblerait aussi que « Zitouna » fasse référence à Sainte-Olive (citée par Ibn Abi-Dinar).

Le tombeau de cette dernière, connue pour avoir été persécutée par l’empereur romain Hadrien, se trouvait dans une basilique sur laquelle la Zitouna fût bâtie.

Ce qui est certain est que la Zitouna a joué un rôle culturel et politique important dans l’histoire de Tunis. Elle a toujours été une école qui a rayonné sur le monde arabe. Des générations d’imams, de Cadis et de penseurs qui ont influencé le cours de l’histoire, sont passés par la Zitouna comme Ibn Arafa, Ibn Khaldoun, le poète Abul-Kacem Chabbi ou encore le penseur Tahar Haddad, qui a œuvré pour la libération des femmes tunisiennes.