Bani Harits bin Ka'ab merupakan kabilah terkemuka yang tinggal di Najran, Yaman, suatu daerah yang mayoritas penduduknya memeluk agama Nashrani. Mereka juga ahli dalam peperangan, dan jarang terkalahkan dalam pertempuran yang diterjuninya, karena itu mereka cenderung memiliki kesombongan dan merasa lebih tinggi dari kabilah lainnya.
Pada tahun 10 hijriah, Nabi SAW mengirim suatu pasukan yang dipimpin Khalid bin Walid kepada kabilah tersebut. Beliau berpesan agar menyeru mereka untuk memeluk Islam selama tiga hari, kalau mereka menolak barulah boleh diperangi. Khalid melaksanakan tugas tersebut, dan ternyata kabilah Bani Harits bin Ka'ab menerima seruan Khalid untuk memeluk Islam. Maka ia tinggal beberapa hari di sana mengajarkan beberapa pokok ajaran Islam.
Setelah merasa cukup memberikan pengajaran dan mereka telah melaksanakan pokok-pokok peribadatan yang ditentukan, Khalid mengirim surat kepada Nabi SAW, mengabarkan keislaman kabilah tersebut, dan juga menjelaskan beberapa karakteristik Bani Harits bin Ka'ab itu. Nabi SAW mengirim surat balasan, yang memerintahkan agar mereka mengirimkan utusan menghadap Nabi SAW, termasuk Khalid bin Walid.
Berselang beberapa hari, Nabi SAW melihat suatu rombongan memasuki kota Madinah menuju Masjid Nabi, beliau berkata, "Siapakah kaum ini, yang wajahnya seperti orang-orang India…!!"
Salah seorang sahabat berkata, "Wahai Rasulullah, mereka adalah Bani Harits bin Ka'ab..!"
Khalid dan beberapa utusan itu, yang merupakan para pemimpin Bani Harits bin Ka'ab ini segera menghadap Rasulullah SAW. Mereka ini adalah Qais bin Hushain, Yazid bin Abdul Madan, Yazid bin Mahjal, Abdullah bin Qirad, Syaddad bin Abdullah al Qinany, dan Amr bin Abdullah adh Dhibaby. Tiba di hadapan beliau, mereka mengucap salam dan berkata, "Kami bersaksi bahwa engkau adalah Utusan Allah, dan kami juga bersaksi bahwa tiada Tuhan selain Allah."
Nabi SAW yang telah mengenali karakter kabilah ini, termasuk informasi dari surat Khalid bin Walid, memberi reaksi yang tidak seperti biasanya, yakni menyambut gembira keislamannya. Beliau justru berkata, "Aku juga bersaksi bahwa tiada Tuhan selain Allah, dan sesungguhnya aku adalah utusan Allah…!!"
Beberapa detik kemudian beliau berkata lagi, "Kaliankah orang-orang yang bila dicegah, justru kalian terus maju….??" Mereka tidak menjawab. Beliau mengulanginya sampai tiga kali, tetapi tetap saja mereka tidak menjawab. Baru setelah beliau mengulang untuk ke empat kalinya, Yazid bin Abdul Madan menjawab, bahkan ia mengulang-ulangnya sampai empat kali, "Benar, ya Rasulullah, kami adalah orang-orang yang bila dicegah, justru akan maju terus…!!"
Setelah itu Nabi SAW bersabda, "Jika saja Khalid tidak menulis surat kepadaku bahwa kalian telah memeluk Islam tanpa perlawanan, niscaya aku akan melemparkan kepala kalian di bawah telapak-telapak kaki kalian…"
Tentu tidak benar-benar seperti itu maksud Nabi SAW kalau saja mereka tidak memeluk Islam. Tetapi beliau menyampaikan perkataan tersebut untuk mengobati dan menawarkan (menetralisir) kesombongan dan arogansi mereka. Namun demikian, Yazid bin Abdul Madan, mewakili rekan-rekannya berkata, "Ketahuilah, demi Allah kami tidak berterima kasih kepadamu, dan tidak juga kepada Khalid…!!"
Nabi SAW berkata, “Kepada siapa kalian berterima kasih?"
"Wahai Rasulullah, kami hanya berterima kepada Allah yang telah memberikan hidayah kepada kami dengan perantaraan engkau…!!" Walaupun sebenarnya "tidak pantas" untuk tidak berterima kasih kepada Nabi SAW atas hidayah Allah yang telah mereka terima, tetapi beliau tidak mempermasalahkannya, bahkan membenarkan jawaban mereka. Kemudian beliau bertanya lagi, "Dengan sebab apakah kalian mengalahkan siapa saja yang memerangi kalian?"
Kali ini mereka memberikan jawaban dengan nada yang berbeda. Pertanyaan yang agak memuji ini justru menimbulkan "rasa malu" untuk menonjolkan diri di hadapan Rasulullah SAW. Mereka berkata, "Kami tidak pernah mengalahkan siapapun..!!"
Tetapi Nabi SAW mengulangi dan menegaskan pertanyaan beliau, "Tidak, bahkan kalian selalu saja mengalahkan mereka yang memerangi kalian…!!" Dengan sikap merendah, mereka menjawab, "Wahai Rasulullah, kami selalu mengalahkan siapa saja yang memerangi kami, karena kami selalu bersatu padu, tidak berpecah belah, dan kami tidak pernah mendahului melakukan kedzaliman kepada siapapun...!"
Nabi SAW merasa puas dengan jawaban tersebut. Beliau menerima syahadat dan ba'iat mereka dengan baik dan menetapkan Qais bin Hushain sebagai amir (pemimpin) kabilah Bani Harits bin Ka'ab ini.
