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