Au VIIIe siècle, Narbonne dispose toujours des murailles héritées de l'époque romaine, chantées par l'évêque Sidoine Apollinaire en 465. Selon une histoire locale connue des Narbonnais, les Sarrasins seraient entrés dans la ville par surprise, à l'automne 719, profitant de l'ouverture des portes en cette période de vendanges. Ce qui expliquerait pourquoi la ville, en dépit de ses ouvrages défensifs, fut si facilement conquise et si longue à reprendre. Le chef musulman fit mettre à mort les hommes ayant tenté de défendre la cité, déporter leurs femmes et enfants en Espagne et laissa une petite garnison[3]. En 734[4] Yusuf al Fihrî arriva en poste à Narbonne et consolida l'autorité du pouvoir califal sur la région puis, en 735, conquiert Arles grâce au ralliement de Mauronte, duc de Marseille. À ce moment-là les Francs mettent le siège devant Narbonne.
Les géographes arabes ont gardé le souvenir de la Narbonne musulmane, comme Zuhrî, au XIIe siècle qui donne une description de la ville à cette époque :
« Sur la côte, à l'est de Barshalûna (Barcelone), il y a la ville d’Arbûna (Narbonne). C'est le point extrême conquis par les musulmans sur le pays des Francs. On y trouvait la statue sur laquelle était inscrit : « Demi-tour, enfants d'Ismaël, ici est votre terme ! Si vous me demandez pourquoi, je vous dirai ceci : si vous ne faites pas demi-tour, vous vous battrez les uns les autres jusqu'au jour de la Résurrection. » Cette ville est traversée en son milieu par un grand fleuve, c'est le plus grand fleuve du pays des Francs ; un grand pont l'enjambe. Sur le dos de l'arche, il y a des marchés et des maisons. Les gens l'utilisent pour aller d'une partie de la ville à l'autre. Entre la ville et la mer, la distance est de deux parasanges [environ 10 km]. Les navires venant de la mer remontent le fleuve jusqu'en aval de ce pont. Au centre de la ville, il y a des quais et des moulins construits par les anciens, personne ne pourrait plus en bâtir de semblables. »
Après la défaite de l'armée sarrasine à la bataille de la Berre, seule la garnison enfermée dans la citadelle résiste, mais son sort est scellé. La population locale est en ébullition, entre 752 et 759 les conflits sont incessants entre francs, sarrasins et wisigoths. En 756 Saragosse se soulève contre les omeyyades. Le califat ne peut rien pour sa garnison de Narbonne à l'approche de Pépin le Bref en 759.
Califat omeyyade
