سنة عشر إلى بني الحارث بن كعب بنجران، وأمره أن يدعوهم إلى الإسلام قبل أن يقاتلهم، ثلاثا، ففعل، فاستجاب له من هناك من بلحارث بن كعب، ودخلوا فيما دعاهم إليه، ونزل بين أظهرهم يعلمهم الإسلام، وشرائعه وكتاب الله وسنة نبيه صلى الله عليه وسلم، وكتب بذلك إلى رسول الله صلى الله عليه وسلم وبعث به مع بلال بن الحارث المزني، فجعل بلال بن الحارث المزني يخبره عما وطئوا وإسراع بني الحارث إلى الإسلام، فكتب رسول الله صلى الله عليه وسلم إلى خالد: أن بشرهم، وأنذرهم، وأقبل ومعك وفدهم، فقدم خالد ومعه وفدهم، وفيهم يزيد بن عبد المدان، وقيس بن الحصين، فقال: من هؤلاء الذين كأنهم رجال الهند؟ فقيل: بنو الحارث بن كعب، فسلموا على رسول الله صلى الله عليه وسلم، وشهدوا أن لا إله إلا الله وأن محمدا رسول الله، فأجازهم بعشر أواق، وأجاز قيس بن الحصين باثنتي عشرة أوقية ونشا، وأمره رسول الله صلى الله عليه وسلم على بني الحارث بن كعب، ثم انصرفوا إلى قومهم في بقية شوال، فلم يمكثوا بعد رجوعهم إلى قومهم إلا أربعة أشهر، حتى توفي رسول الله صلى الله عليه وسلم وعليه رحمته وبركاته.

وفي حديث آخر، أنها لما قدموا على رسول الله صلى الله عليه وسلم وأسلموا، قال رسول الله صلى الله عليه وسلم: أنتم الذين إذا زجروا استقدموا، فسكتوا، فلم يراجعه منهم أحد، ثم قال: أنتم الذين إذا زجروا استقدموا، فسكتوا، فلم يراجعه منهم أحد، ثم قال: أنتم الذين إذا زجروا استقدموا، فسكتوا فلم يراجعه منهم أحد، ثم أعادها الرابعة: أنتم الذين إذا زجروا استقدموا، أربع مرات، فقال يزيد بن عبد المدان: نعم يا رسول الله، نحن الذين إذا زجروا استقدموا، نعم يا رسول الله نحن الذين إذا زجروا استقدموا، نعم يا رسول الله، نحن الذين إذا زجروا استقدموا، نعم يا رسول الله، نحن الذين إذا زجروا استقدموا. فقال رسول الله صلى الله عليه وسلم: لولا أن خالدا لم يكتب إلي أنكم أسلمتم ولم تقاتلوا لألقيت رؤوسكم تحت أقدامكم. فقال يزيد بن عبد المدان: إنا والله يا رسول الله ما حمدناك، وما حمدنا خالد بن الوليد، فقال صلى الله عليه وسلم: فمن حمدتم؟ قالوا: حمدنا الله الذي