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