Wikipedia
Madh'hij ( Arabic: مذحج) also spelled Math'hij is famous large Qahtanite Arabic dynasty. It is located in south and central arabia. This dynasty participated in the Arabic Islamic conquest and was a major factor in the conquest of Persian empire and Iberian Peninsula. It is also found in Mosel and in Levant and Iberian Peninsula.
Madhhij descend from a man named Madhhij who was one of 10 sons of a man named Saba' whose name was 'Abdu Shams; but the reason why he was called Saba' was that he was the first among the Arabs to take captives. He was the son of Yashjub bin Ya'rub b. Qahtan son of Tayman son of Qaydar son of Ishmael. Six of the sons of Saba' (went to Yemen): Kindah, Madhhij , Ashari ,Himyar, Anmar and Azd, while four sons went to Shaam (Greater Syria) Judham Lakhm Amila and Gassan
the Islamic prophet, Muhammad said that most people in Paradise will be from Madhhij and Aslam and Gafar.
al-Hamdani cited Madhhij 30 times in his book "Sifat Jazirat al Arab: Description of the Arabian Peninsula" as a Genuine Arabic dynasty with branches like Nukha and Zubaid Ruha and Hada (best archers among the Arabs) that has famous Historical personalities such as the Arabian knight king of Yemen Amru bin Ma'adi Yakrib al-Zubaidi al-Madhhiji who became Muslim and Malik Ashtar al-Nakh'ei a close friend of the Prophet Muhammad and a military leader with Ali ibn Abi Talib in the battle of Siffin, and Madhhij tribe later fought the Qarmatians under leadership of Abul Ashira in Yemen and Malik ibn Marara a-Rahawi, and the commentaries on al-Hamdani's book shows that they still live in the same towns and places as Hamadani described them in his book dated 900 AD, 1100 hyears ago.
Madhhij is mentioned in Namara inscription, a memorial of the Nasrid king of al-Hira Imru ’al-Qays bin ‘Amr (died in 328), “king of all the Arabs”, boasted of having launched a raid against Madhhij, reaching “ Najran" city of Shammar (the Himyarite king Shammar Yahri'sh) . The same story is mentioned in detail in Wahb ibn Munabbih in his book of Pre-Islamic saga and lore "The Book of The Crowns of Himyar Kings"
There was a prophet from Madhhij who appeared in Yemen in the last year of Muhamma's life and was from the Ans tribe a part of Madhhij, and his name was Aswad Ansi. He was ousted by the Persian Governor who turned Muslim working for Muhammad. al-Aswad was nicknamed Dhu l'Khimar "the man in the veil". Some said he was very ugly to see his face.
Before Islam, Madhhij had its own Idol that they used to bring in the yearly pilgrimage to Kaaba before Islam (Pagan Arabs before Islam) and they used to make Talbiya specific to Madhhij for that Idol in which they encircle Kaaba several times and plead their Madhhij' Talbiya to Allah to let that Idol be put around the Kaaba. The Arabs are said to inherited Kaaba from Ibrahim who named it Beit Allah, Bethel aka the house of God) but in much later ages they started worshipping idols and then they brought the idols to Kaaba to bless their Idols by God.
Madhhij name was found in the Namara inscription dated 330 AD.
The tribe of Madh'hij was described as spearmens in praising their positive aspect