Les Banû al-Khazraj ou Banû Khazraj étaient une tribu arabe de l'ère médinoise. Comme les Banû Aws, les Banû Khazraj appartenaient aux Arabes du sud ou Yéménites, issus de la descendance de Qahtan dont la célébrité tient surtout au rôle que ses membres ont joué auprès de Mahomet pendant la période médinoise. Aws et Khazraj étaient connus comme Banū Qayla (بنو قيلة ) dans l'ère pré-islamique. Au début du , le Barrage de Marib s'effondre une première fois. Cette catastrophe, conjuguée avec le changement des routes de commerces dû à la présence des Romains qui préfèrent les routes maritimes aux routes terrestres, va provoquer une première vague d'émigration des tribus arabes du Yémen vers le nord. Dès la fin du , des tribus arabes originaires du Yémen fondent la ville d'Al-Hira auprès de la moderne Koufa créant l'empire lakhmide vassal des Sassanides. Cet empire tombe aux mains des Sassanides en 605. Ces tribus arabes installées aux frontières des deux empires romain et sassanide se mettent au service de l'un ou l'autre de ces empires et créent des États tampons. Les Ghassanides convertis au christianisme monophysite ont fondé un royaume arabe dans la Jordanie actuelle. Ils furent longtemps des vassaux de l'Empire byzantin et contribuèrent à contenir les Perses sassanides hors des frontières de l'Empire byzantin. À son apogée le royaume ghassanide s'étendait du sud de la Syrie jusqu'à la ville de Yathrib (actuellement Médine) en Arabie saoudite. Vers 300, les tribus errantes des Banû Aws et des Banû Khazraj arrivent à Yathrib. Elles concluent une alliance avec les tribus juives qui y sont installées depuis sans doute le : Banû Qaynuqâ', Banû Nadîr et les Banû Qurayza. Progressivement leur importance relative dans l'oasis augmente. Ils envient la prospérité des juifs. Ces nouveaux venus obtiennent le soutien du roi chrétien ghassanide Al-Harith I ibn Th`alabah (287-307). Ils supplantent les tribus juives qui deviennent vassales vers le . Les Aws, les Khazraj avaient coutume de se rendre en pèlerinage dans divers lieux dont La Mecque.