سال دهم هجرت بود. هنوز مردم یمن در بت پرستی باقی بودند و به اسلام نگرویده بودند. پیامبر صلی الله علیه و آله و سلم خالد بن ولید را با جمعی از مسلمانان از جمله براء بن عازب به یمن فرستاد تا مردم را به اسلام دعوت کنند، خالد با همراهان خود مدت شش ماه در یمن بود ولی از مردم آنها حتی یک نفر هم مسلمان نشده بود، این خبر به پیامبر صلی الله علیه و آله و سلم رسید. آن حضرت رنجیده خاطر شد هماندم علی (علیه‏السلام) را به حضور طلبید و به او فرمود: به سوی یمن برو و خالد و همراهانش را به مدینه بفرست و اگر کسی از همراهان خالد خواست به دنبال تو باشد از او جلوگیری نکن. علی (علیه‏السلام) به یمن رفت خالد و همراهانش را به مدینه فرستاد ولی چند نفر از جمله براء بن عازب با علی (علیه‏السلام) در یمن ماند. براء می‏گوید: وقتی که ما همراه علی (علیه‏السلام) به اوائل یمن رسیدیم مردم یمن از ورود علی (علیه‏السلام) باخبر شدند. نزد آن حضرت اجتماع کردند. امام علی (علیه‏السلام) نماز صبح را به جماعت خواند، و بعد از نماز سخنرانی کرد. سپس نامه رسول خدا صلی الله علیه و آله و سلم به مردم یمن را برای آنها خواند، آنها چنان شیفته کلام بلند علی (علیه‏السلام) شدند که همان روز قبیله همدان که جمعیتشان از همه قبایل یمن بیشتر بود مسلمان شدند عی (علیه‏السلام) این خبر مسرت بخش را در ضمن نامه‏ای به پیامبر صلی الله علیه و آله و سلم گزارش داد. پیامبر صلی الله علیه و آله و سلم وقتی خبر را شنید بسیار شاد شده و سجده شکر بجای آورد. سپس برخاست و فرمود: سلام و درود بر قبیله همدان بعد از آن قبیله سایر قبائل نیز پیاپی آمدند و مسلمان شدند.(254)