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