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