They are descendants of Malik al-Ashtar al-Nakh'ei who fought with Ali ibn Abi Talib, the cousin of the Islamic prophet Muhammad.
After they became Muslims, Al-Nakh'a continued their ancestry with their cousins, the tribe of Azd (Madhhij's brother), who lived in Makkah called Khuza'a (خزاعة) named after Khuza’a (also named Haritha) Ibn Amr Ibn Muzaqiba of Al-Azd the major Qahtani tribe.
Khuza'a tribe fought with Muhammad against the pagans and infidels Banu Bakr who tried to conquer Makka.
Sulaiman bin Kuthayer who is one of the Abbasid supporters descended from Bani Malik.
The territory of their major offshoot, Al-Ali tribe, extends from al-Diwanylah in the north to al-Rumaitha to the south.