لقد مكّن اقبال اهل الحجاز على الاسلام، وأمن النبي (صلى الله عليه واله) جانب القبائل العربية، مكّن النبي من العمل على مدّ شعاع الاسلام إلى البلاد المتاخمة للحجاز.
فكان أول ما فعل (صلى الله عليه واله) في هذا الصعيد هو بعث أحد أصحابه العلماء وهو معاذ بن جبل  الى اليمن ليبلّغ إلى اهلها نداء التوحيد ويشرح لهم معالم الاسلام وتعاليمه المقدسة، وقد أوصاه بوصايا كثيرة ومفصلة منها قوله (صلى الله عليه واله).
يسّر ولا تعسّر وبشّر ولا تنفّر وإنك ستقدم على قوم من أهل الكتاب يسألونك ما مفتاح الجنة : فقل شهادة أن لا إله الاّ الله وحده لا شريك له.
ويبدو أن معاذا رغم انه كان ملمّا بالكتاب العزيز والسنة النبوية وتعاليمها واحكامها، إلا انه لما سألته امرأة عن حق الزوج على الزوجة لم يملك لها جوابا مقنعا، ولهذا رأى رسول الله (صلى الله عليه واله) بأن يوجه الى اليمن تلميذه المتميز علي بن أبي طالب  (عليه السلام) حتى يتمكن في ضوء دعوته الدائبة، واحاديثه المبرهنة، وما يمتلك من شجاعة أدبية نادرة، وقوة عقلية متميزة من نشر الإسلام العظيم في تلك الربوع.
هذا مضافا إلى أن النبيّ (صلى الله عليه واله) كان قد بعث خالد بن الوليد الى اليمن من قبل ليزيل المشكلات التي كانت تعرقل تقدّم الاسلام في تلك الديار ولكنه لم يوفّق في مدة بقائه لعمل شيء في هذا المجال.
فاستدعا النبي (صلى الله عليه واله) عليا (عليه السلام) وأخبره بأنه يريد أن يذهب الى اليمن ليدعو أهلها إلى الإسلام، وليخمّس ركازهم، ويعلّمهم الاحكام، ويبين لهم الحلال والحرام، وإلى أهل نجران ليجمع صدقاتهم ويقدم عليه بجزيتهم، فقال علي (عليه السلام) بتواضع بالغ : يا رسول الله تبعثني وأنا شاب أقضي بينهم ولا أدري ما القضاء أي ما فعلته قبل هذا.
فضرب رسول الله (صلى الله عليه واله) بيده في صدر عليّ (عليه السلام) وقال : اللهم اهد قلبه وثبّت لسانه.
ثم قال (صلى الله عليه واله) : يا عليّ لا تقاتلنّ أحدا حتى تدعوه وأيم الله لئن يهدي الله على يديك رجلا خير لك ممّا طلعت عليه الشمس وغربت ولك ولاؤه يا علي.
ثم أوصاه (صلى الله عليه واله) بوصايا أربع هامة إذ قال : يا علي أوصيك :
1 ـ بالدّعاء فإن معه الإجابة.
2 ـ وبالشكر فانّ معه المزيد.
3 ـ وإيّاك أن تخفر عهدا أو تعين عليه.
4 ـ وأنهاك عن المكر، فانه لا يحيق المكر السيّئ إلاّ بأهله، وأنهاك عن البغي، فانه من بغي عليه لينصرنه الله.
ولقد بقي علي (عليه السلام) يقوم بالقضاء طيلة ايام اقامته في اليمن بصورة عجيبة محيّرة، وقد دونت اكثر اقضيته في كتب التاريخ والحديث.
هذا ويروي البراء بن عازب وكان من الذين صحبوا عليا (عليه السلام) في سفره هذا الى اليمن انه لما انتهى علي (عليه السلام) ومن معه إلى أوائل أهل اليمن، وبلغ القوم الخبر، فخرجوا إليه صفّ عليّ (عليه السلام) الجنود الذين كانوا قد استقروا هناك من قبل بقيادة خالد بن الوليد، ثم صلّى بهم صلاة الفجر، ثم دعا قبيلة همدان كلّها، وكانت اكبر القبائل اليمنية، ليقرأ عليهم كتاب رسول الله (صلى الله عليه واله)، فحمد الله، واثنى عليه، ثم قرأ على القوم كتاب رسول الله (صلى الله عليه واله) فأسلمت همدان كلها في يوم واحد متأثرة بجلال المشهد، وحلاوة البيان، وعظمة المنطق النبوي، فكتب امير المؤمنين (عليه السلام) بذلك إلى رسول الله (صلى الله عليه واله) فلمّا قرأ كتابه استبشر وابتهج وخرّ ساجدا شكرا لله تعالى ثم رفع رأسه وجلس وقال : السلام على أهل همدان. 
السلام على أهل همدان.
ثم تتابع ـ على أثر اسلام همدان ـ أهل اليمن على الاسلام.