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