Banu Khutheer of Al Hajaj Tribes (آل خضير من قبايل حجاج) are a clan that originally goes back to their ancestor Hashid, who in turn comes from the house of Himdaan. And Himdaan, the Great Great Ancestor of the Hajaj Tribes accepted Islam from Ali bin Abi Taleb.
Muhammad sent Khalid bin Al-Waleed before sending Ali to Yemen. However the clans from the House of Himdaan did not accept Islam at first. Ali taught Islam to the tribes of Yemen where Himdaan was accepted.
Banu Khutheer are also known Qahtan Arabs or Qahtanites.