النبي ﷺ مع مالك بن مرارة الرهاوي أيضا بإسلامه وإسلام ملوك اليمن من أبناء عبد كلال ومفارقتهم الشرك وأهله.
وقد كتب النبي ﷺ إلى أهل اليمن كتابا يخبرهم فيه بشرائع الإسلام وفرائض الصدقة والمواشي والأموال، ويوصيهم بأصحابه ورسله خيرا، وكان رسوله إليهم معاذ بن جبل ومالك بن مرارة.
وقد حمل معاذ ومالك هذا الكتاب النبوي إلى اليمن بعد شهر رمضان من السنة التاسعة الهجرية: في شهر شوال أو شهر ذي القعدة من السنة التاسعة الهجرية، فهذا هو الوقت المناسب لإرسال هذا الكتاب النبوي الجوابي على رسالة ملوك اليمن التي حملت نبأ إسلامهم.