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