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