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