وأخرج البيهقي عن البَرَاء رضي الله عنه أن رسول الله صلى الله عليه وسلم بعث خالد بن الوليد إلى أهل اليمن يدعوهم إلى الإِسلام. قال البراء: فكنت فيمن خرج مع خالدِ بن الوليد، فأقمنا ستة أشهر يدعوهم إلى الإِسلام فلم يجيبوه، ثم إن رسول الله صلى الله عليه وسلم بعث علي بن أبي طالب وأمره أن يقفل خالدًا إِلا رجلًا كان ممَّن مع خالد فأحب أن يَعِقِب مع علي فليَعقبْ معه. قال البراء: فكنت فيمن عَقَب مع علي. فلما دَنوْنا من القوم خرجوا إِلينا، ثم تقدَّم فصلَّى بنا علي، ثم صفَّنا صفًا واحدًا ثم تقدم بين أيدينا وقرأ عليهم كتاب رسول الله صلى الله عليه وسلم فأسلمت همْدان جميعًا، فكتب علي إلى رسول الله صلى الله عليه وسلم بإسلامهم. فلما قرأ رسول الله صلى الله عليه وسلم الكتاب خرّ ساجدًا ثم رفع رأسه فقال: «السلام على هَمْدان. السلام على هَمْدان» . ورواه البخاري مختصرًا. كذا في البداية.
وذكر ابن إسحاق: أن رسول الله صلى الله عليه وسلم بعث خالد بن الوليد رضي الله عنه إلى بني الحارث بن كعب بنجران، وأمره أن يدعوَهم إلى الإِسلام قبل أن يقاتلهم ثلاثًا، فإن استجابوا فأقبل منهم وإن لم يفعلوا فقاتلهم. فخرج خالدٌ حتى قدم عليهم، فبعث الركبان يضربون في كل وجه ويدعون إلى الإِسلام ويقولون: «أيها الناس، أسلموا تسلموا» فأسلم الناس؛ ودخلوا فيما دُعُوا إِليه. فأقام فيهم خالد يعلمهم الإِسلام كتابَ الله وسنّة نبيه صلى الله عليه وسلم كما أمره رسول الله صلى الله عليه وسلم إن هم أسلموا ولم يقاتلوا. ثم كتب خالد بن الوليد رضي الله عنه إلى رسول الله صلى الله عليه وسلم