According to Ibn Ishaq, the Messenger of God (peace be upon him) sent Khālid b. al-Walīd to the Banū Ḥāris b. Kaʿb tribe in the month of Rabīʿ al-Ākhir or Jumādā al-Awwal of the tenth year of the Hijra. They were residing in Najrān. He commanded him to invite them to Islam for three days before engaging in battle, to accept their conversion if they responded to the invitation, and to fight them otherwise.
Khālid set out and, upon arrival, sent mounted men to them from every direction. They invited them to Islam, saying: "O people! Become Muslim so that you may attain safety." Thereupon, they accepted Islam and entered the religion to which they were called. Khālid remained among them, teaching them Islam, the Book of Allah, and the sunnah (prophetic practice) of the Prophet. The Messenger of God (peace be upon him) had commanded Khālid that, if they became Muslim, he should stay among them and teach them Islam.
Then Khālid b. al-Walīd wrote the following letter to the Messenger of God (peace be upon him):
"In the name of Allah, the Most Gracious, the Most Merciful.
From Khālid b. al-Walīd to the Messenger of Allah, Muḥammad. O Messenger of Allah, may Allah's peace, mercy, and blessings be upon you. I praise Allah, besides Whom there is no deity worthy of worship. Now then, O Messenger of Allah, you sent me to the Banū Ḥāris b. Kaʿb tribe and commanded me that, when I reached them, I should not fight them for three days, but invite them to Islam. If they became Muslim, I should remain among them, accept their Islam, and teach them Islamic knowledge, the Book of Allah, and the sunnah of His Prophet. If they did not become Muslim, I should fight them. I came to them and for three days invited them to Islam. As you commanded, I sent horsemen to them, who conveyed: 'O Banū Ḥāris tribe, become Muslim so that you may attain safety.'
They became Muslim and there was no fighting. I am now residing among them, commanding them to do what Allah has commanded and forbidding them from what Allah has prohibited. I am teaching them the fundamentals of Islam and the sunnah of the Prophet (peace be upon him). I will remain here until the Messenger of God writes to me. May Allah's peace, mercy, and blessings be upon you, O Messenger of Allah."
The Messenger of God (peace be upon him) then sent him the following letter:
"In the name of Allah, the Most Gracious, the Most Merciful.
From Muḥammad, the Messenger of Allah, to Khālid b. al-Walīd. Peace be upon you. I praise Allah, besides Whom there is no deity worthy of worship. Now, your letter has reached me with your messenger. You inform me that the Banū Ḥāris b. Kaʿb tribe accepted Islam without being fought, that they accepted the Islam to which you invited them, that they bore witness that there is no deity but Allah and that Muḥammad is the servant and Messenger of Allah, and that they were guided by Allah's hudā (guidance). Therefore, give them glad tidings and warn them. Come, and let their envoys come with you. May Allah's peace, mercy, and blessings be upon you."
Thereupon, Khālid came to the Messenger of God (peace be upon him), accompanied by the envoys of the Banū Ḥāris b. Kaʿb. Among them were Qays b. Ḥusayn Dhū'l-Ghussah, Yazīd b. ʿAbd al-Maddān, Yazīd b. Muḥajjal, ʿAbdullāh b. Kurad al-Ziyādī, Shaddād b. ʿAbdullāh al-Kanānī, and ʿAmr b. ʿAbdullāh al-Dibbābī.
When they came to the Messenger of God (peace be upon him) and he saw them, he said:
– Who are these people? They look like Indian men.
It was said:
– O Messenger of God, these are men from the Banū Ḥāris b. Kaʿb tribe.
When they stood before the Messenger of God (peace be upon him), they greeted him and said:
– We bear witness that you are the Messenger of Allah and that there is no deity but Allah.
The Messenger of God replied:
– I myself bear witness that there is no deity but Allah and that I am the Messenger of Allah.
After this testimony, the Messenger of God asked them:
– Were you the ones who advanced when others were prevented?
They remained silent, and none of them answered. He repeated the question a second time, but again none replied. He repeated it a third time, and still no one answered. When he asked a fourth time, Yazīd b. ʿAbd al-Maddān said:
– Yes, O Messenger of God, we were the ones who advanced when others were prevented.
Yazīd repeated this statement four times. Thereupon, the Messenger of God (peace be upon him) said:
– Had Khālid not written to me that you had become Muslim and that there was no fighting, I would certainly have struck off your heads and laid them at your feet.
Upon this, Yazīd b. ʿAbd al-Maddān said:
– By Allah, we do not praise you, nor Khālid.
– Then whom do you praise?
– O Messenger of God, we praise Allah, the Mighty and Majestic, Who has guided us to hudā (guidance) through you.
– You have spoken the truth.
The Messenger of God (peace be upon him) then continued:
– In the time of ignorance, how did you prevail over those who fought you?
– We never prevailed over anyone.
– No, you did prevail over those who fought you.
– O Messenger of God, we prevailed over those who fought us as follows: we would gather and not disperse, and we were never the first to commit injustice against anyone.
– You have spoken the truth.
After this, the Messenger of God (peace be upon him) appointed Qays b. Ḥusayn as their leader.
The delegation of the Banū Ḥāris tribe returned to their people at the end of Shawwāl or the beginning of Dhū al-Qaʿda.
After the return of the delegation, the Messenger of God (peace be upon him) sent ʿAmr b. Ḥazm to them to teach them religious rulings, the sunnah, and Islamic principles, and to collect their zakāt (obligatory alms). He wrote a letter and sent it with him to the Banū Ḥāris b. Kaʿb tribe, in which the commands and obligations were written."