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