Les Vandales à la suite de la mise à sac d’une grande partie de l’Europe, et notamment après l’invasion qui ruina la Gaule (407-409) et le premier pillage de Rome (24 Août 410), furent battus par les Wisigoths, et se virent ainsi contraints à chercher refuge dans d’autres territoires pour se réunifier à nouveau et régénérer leurs forces.

Ils traversent donc le détroit de Gibraltar et débarquent aussi en Tripolitaine (l'actuelle Lybie, dénommée Regio Tripolitana par les Romains à partir du III siècle) avec une flotte de 80.000 hommes. Sous Genséric (389-477), et qui fût leur roi entre 428 et 477, les Vandales conquièrent ainsi la Numidie (Est de l’actuelle Algérie), la Bysacène (sud de la Tunisie) et la Proconsulaire (nord de la Tunisie).

La résistance d’Hippone (Hippo Regius, l'actuelle Annaba) et Cirta (Constantine) à leur soumission obligea les Vandales à accepter un Traité de Trois (435), mais sitôt que la trêve expira (le 18 octobre 439), ces derniers s'emparent de ces deux villes, prennent Carthage plus à l'Est, dont ils font ensuite la capitale de leurs territoires d’Afrique, avant de se diriger vers le Sud. De par leur conquête de la Corse, la Sardaigne, les Baléares et temporairement celle de la Sicile, les Vandales se firent aussi les maîtres de la mer en pillant les côtes de la Méditerranée. Ils ne réussissent cependant pas à établir un état stable et furent incapables d’établir la fusion entre Romains et Barbares (Barbare est le nom attribué par les Gréco-Romains à tous les peuples ne parlant pas leur langue, et ne suivant pas leurs mœurs et coutumes).

Pendant ce temps, l'empereur Honorius (Flavius Honorius, 384-423) envoie le comte Boniface (?-432), Général du Bas-Empire pour gouverner l'Afrique. Ayant été injustement disgracié à la suite d'intrigues montées par Aétius (396-454) Boniface refuse de quitter son gouvernement d'Afrique, et bloque l'approvisonnement en blé Africain de Rome. Il s'allia ensuite à Genséric, roi des Vandales, contre les Romains mais il réalisa l'énormité de son erreur quand il ne put arrêter plus tard l'avance de ces Barbares. Ainsi, battu par Genséric, il dut céder les trois Maurétanie, Sétifienne, Césarienne (dont la ville principale est Césarée, actuelle Cherchell), Tingitane (Tingis, actuelle Tanger) et s'enfuit en Italie où il mourut à la suite d'un combat avec Aétius en 432.

Auzia, durant cette période, eut donc à subir le même sort que ses villes sœurs d’Afrique du Nord, c'est-à-dire le joug des Vandales pendant 106 ans. Plusieurs révoltes élevées par ses habitants contres ces barbares ne se soldèrent néanmoins d'aucun succès et se virent au contraire réprimer avec férocité et de façon sanglante avec comme résultat la destruction et la mise à feu de bon nombre d'édifices publics ou privés.

Vint ensuite la période Byzantine marquant la fin du règne des Vandales qui furent chassés d’Afrique du Nord. Les Byzantins, héritiers des Romains, occupent donc l'Afrique militairement de 534 à 647. Les Arabes lors de leurs conquêtes Islamiques qui atteignent l’Algérie de son coté oriental chassent à leur tour les Byzantins dans la seconde moitié du VIIè siècle vers 697 (bataille de la Kahina près de Tébessa).

Auzia n’est cependant pas mentionnée en relation avec quelque fait avant cette époque. L’administration de la ville est en tout cas assurée par les Berbères, en domination, et qui sont toujours en insurrection dans le Nord de l'Afrique. Il n’existe non plus aucune mention du déclin ou de la disparition de cette ville, que ce soit dans des notes écrites ou orales, d’évènements ayant marqué le sort de la ville durant la période allant du septième au douzième siècles.

Auzia eut à se défendre contre l'invasion des Maures qui, finalement, restèrent maîtres de l'Afrique. La religion musulmane remplaça la religion chrétienne et Auzia dut, comme ses compagnes subir son nouveau sort, la langue des Maures, leurs mœurs, leur religion y furent imposés. Sous la domination Arabe, le Municipe d'Auzia devient "Sour El Ghozlane" ou Rozlan (rempart des gazelles), la gazelle aux environs de la ville, n'existant plus à l'arrivée des colons français qu'à l'état de légende.