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