I Khuza'a , o Banu Khuza'a, formano uno dei rami della tribù sudarabica ( yemenita ) degli Azd .
La maggior parte dei tradizionalisti fa risalire le origini della tribù ad ʿAmr soprannominato Luhaiy, e concorda sul fatto che una volta, insieme agli altri rami dell'Azd, lasciò lo Yemen per trasferirsi a nord. 'Amr ibn Luhay e il suo clan si stabilirono intorno alla Mecca . Siamo in grado di stabilire la data di questa struttura nel corso del V ° secolo, anche se il posto tradizionalisti ad una data anteriore, dando in particolare vive a lungo alcuni dei suoi leader.
Essendo diventati i padroni del territorio della Mecca, i Khuza'a permisero ai discendenti di Ismaele di rimanere lì in pace nella misura in cui non si schierarono nelle liti tra clan che portarono a questa insediamento. Un'epidemia l'anno successivo alla cattura della città decima la popolazione. Un altro clan Azd ha colto l'occasione per stabilirsi lì. I legami coniugali uniscono i due clan.
Il capo della Khuza'a di nome Rabi`a fa rivivere i riti del pellegrinaggio prendendosi cura del benessere dei pellegrini. Avremmo dovuto anche mettere un primo idolo nella Ka`ba e in particolare per aver portato l'idolo di Hubal da Hit in Mesopotamia . Questo idolo è uno di quelli che ancora esistevano ai tempi di Maometto . L'ultimo membro della tribù a regnare sulla Mecca è Hulail che dà sua figlia Hobba (Hubbaiy) in sposa a Qusay, allora capo del clan Quraysh . Hulail dà le chiavi della Ka`ba a sua figlia e suo genero, rendendoli così guardiani del santuario. I membri del clan Khuza'a si oppongono, ne segue una dura battaglia tra i due clan. La rivalità si conclude con un accordo: poiché il numero delle vittime nel clan Khuza'a è superiore a quello delle vittime nel clan Quraysh, la vittoria è concessa a quest'ultimo.
La fine del dominio dei Khuza'a corrisponde all'inizio di quello dei Quraysh. Un'altra versione meno gloriosa della storia racconta che l'ultimo guardiano Khuza'a della Ka`ba vendette il suo titolo a Qusay , per una buccia di vino. Questa versione è raccontata da Hicham ibn al-Kalbi in un libro intitolato Kitab al-mathâlib "Libro della denigrazione".
Il gran numero di persone che affermano di essere della discesa del Khuza'a può suggerire che essi erano forse più numerosi al tempo di Maometto rispetto a quanto suggerito dal loro piccolo numero fra le compagne dei profeti di Islam. ( Sahaba ). A quel tempo, forse furono respinti nei dintorni della Mecca dai Quraish.